Number of Connected Components in an Undirected Graph

Share

Find number of connected components in an undirected graph of n nodes.

Example 1
Input: n=5, edges=[[0,1],[1,2],[3,4]] → Output: 2
Example 2
Input: n=5, edges=[[0,1],[1,2],[2,3],[3,4]] → Output: 1

Solution Approach

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
Java
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)