Given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 if city i and city j are directly connected, return the total number of provinces (a province is a group of directly or indirectly connected cities).
Example 1
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Explanation: Cities 0 and 1 are connected (one province); city 2 is isolated (a second province).
1 <= n <= 200This is 'count connected components' — a classic Union-Find (Disjoint Set) problem, though DFS/BFS also solves it.
Union-Find tracks which cities belong to the same group efficiently as you process each connection, without needing a full graph traversal per component.
Don't over-invest in a from-scratch union-find with full path compression and union-by-rank for this level of prep — knowing the high-level idea and a working implementation is enough.
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i; // each city starts as its own province
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) union(parent, i, j);
}
}
int provinces = 0;
for (int i = 0; i < n; i++) if (find(parent, i) == i) provinces++; // count distinct roots
return provinces;
}
private int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]); // path compression
return parent[x];
}
private void union(int[] parent, int a, int b) {
int rootA = find(parent, a), rootB = find(parent, b);
if (rootA != rootB) parent[rootA] = rootB;
}Time: O(n^2 * α(n)), α = inverse Ackermann, effectively constant · Space: O(n)