Given an n x n adjacency matrix isConnected where isConnected[i][j]=1 means cities i and j are directly connected, find the number of provinces (connected components).
Input: [[1,1,0],[1,1,0],[0,0,1]] → Output: 2Input: [[1,0,0],[0,1,0],[0,0,1]] → Output: 3
Union-Find: union all pairs (i,j) where isConnected[i][j]==1. Count distinct roots.
- Initialize parent[i]=i.
- For i from 0 to n-1: for j from i+1 to n-1: if isConnected[i][j]==1: union(i,j).
- Count i where find(i)==i.
class Solution {
int[] parent;
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (isConnected[i][j] == 1) union(i,j);
int count = 0;
for (int i = 0; i < n; i++) if (find(i)==i) count++;
return count;
}
private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
private void union(int a, int b) { parent[find(a)]=find(b); }
}
- Time Complexity: O(N^2 * alpha(N))
- Space Complexity: O(N)