Find number of connected components in an undirected graph of n nodes.
Input: n=5, edges=[[0,1],[1,2],[3,4]] → Output: 2
Input: n=5, edges=[[0,1],[1,2],[2,3],[3,4]] → Output: 1
Union-Find: union connected nodes, count remaining roots.
- Initialize parent[i]=i for all i
- For each edge: union both nodes
- Count distinct roots (nodes where parent[i]==i)
- Return count
public int countComponents(int n, int[][] edges) {
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int[] e : edges) {
int ra = find(parent, e[0]), rb = find(parent, e[1]);
if (ra != rb) { parent[ra] = rb; n--; }
}
return n;
}
private int find(int[] parent, int x) {
return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
- Time Complexity: O(n * alpha(n))
- Space Complexity: O(n)