Number of Connected Components in an Undirected Graph

Share

Given n nodes and edges in an undirected graph, return the number of connected components.

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

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