Given n nodes and edges in an undirected graph, return the number of connected components.
Input: n=5, edges=[[0,1],[1,2],[3,4]] → Output: 2Input: n=5, edges=[[0,1],[1,2],[2,3],[3,4]] → Output: 1
Use Union-Find. For each edge, union the two nodes. Count distinct roots.
- Initialize parent[i]=i for all i.
- For each edge (u,v): union u and v.
- Count distinct roots: number of i where find(i)==i.
class Solution {
int[] parent;
public int countComponents(int n, int[][] edges) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int components = n;
for (int[] e : edges) {
int pu = find(e[0]), pv = find(e[1]);
if (pu != pv) { parent[pu] = pv; components--; }
}
return components;
}
private int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
}
- Time Complexity: O(N + E * alpha(N))
- Space Complexity: O(N)