Untitled

mail@pastecode.io avatar
unknown
plain_text
14 days ago
2.8 kB
1
Indexable
Never
import java.util.Scanner;

public class Solution {

	static int time;
	static int bridgesCount;

	public static void main(String[] args) throws Exception {
	//	System.setIn(new FileInputStream("src/protectfam/input.txt"));
		Scanner sc = new Scanner(System.in);

		for (int test = 1; test <= 2; test++) {
			int N = sc.nextInt();
			boolean[][] adjMatrix = new boolean[N][N];

			// Reading the adjacency matrix
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					adjMatrix[i][j] = sc.nextInt() == 1;
				}
			}

			int regions = countRegions(N, adjMatrix);
			int isolatedVillages = countIsolatedVillages(N, adjMatrix);
			int bridges = countBridges(N, adjMatrix);

			System.out.println(regions + " " + isolatedVillages + " " + bridges);
		}

		sc.close();
	}

	private static int countRegions(int N, boolean[][] adjMatrix) {
		boolean[] visited = new boolean[N];
		int regions = 0;

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				regions++;
				dfsRegions(i, N, adjMatrix, visited);
			}
		}

		return regions;
	}

	private static void dfsRegions(int node, int N, boolean[][] adjMatrix, boolean[] visited) {
		visited[node] = true;
		for (int neighbor = 0; neighbor < N; neighbor++) {
			if (adjMatrix[node][neighbor] && !visited[neighbor]) {
				dfsRegions(neighbor, N, adjMatrix, visited);
			}
		}
	}

	private static int countIsolatedVillages(int N, boolean[][] adjMatrix) {
		int isolated = 0;

		for (int i = 0; i < N; i++) {
			boolean hasConnection = false;
			for (int j = 0; j < N; j++) {
				if (adjMatrix[i][j]) {
					hasConnection = true;
					break;
				}
			}
			if (!hasConnection)
				isolated++;
		}

		return isolated;
	}

	private static int countBridges(int N, boolean[][] adjMatrix) {
		boolean[] visited = new boolean[N];
		int[] discovery = new int[N];
		int[] low = new int[N];
		int[] parent = new int[N];

		for (int i = 0; i < N; i++) {
			parent[i] = -1;
		}

		time = 0;
		bridgesCount = 0;

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				dfsBridges(i, N, adjMatrix, visited, discovery, low, parent);
			}
		}

		return bridgesCount;
	}

	private static void dfsBridges(int u, int N, boolean[][] adjMatrix, boolean[] visited, int[] discovery, int[] low,
			int[] parent) {
		visited[u] = true;
		discovery[u] = low[u] = ++time;

		for (int v = 0; v < N; v++) {
			if (adjMatrix[u][v]) {
				if (!visited[v]) {
					parent[v] = u;
					dfsBridges(v, N, adjMatrix, visited, discovery, low, parent);

					low[u] = Math.min(low[u], low[v]);

					if (low[v] > discovery[u]) {
						bridgesCount++;
					}
				} else if (v != parent[u]) {
					low[u] = Math.min(low[u], discovery[v]);
				}
			}
		}
	}
}
Leave a Comment