Number of Connected Components in an Undirected Graph

medium graph union find

Problem

You have a graph with n nodes labeled 0..n-1 and an edge list. Return the number of connected components.

Start with n separate components. For each edge (a, b), union them — if their roots differ, two components merge into one, so decrement the count.

Inputn = 5, edges = [[0,1],[1,2],[3,4]]

Output2

edges (a-b separated by ';')

def count_components(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    count = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            count -= 1
    return count

function countComponents(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
  let count = n;
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) { parent[ra] = rb; count--; }
  }
  return count;
}

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 count = n;
        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra != rb) { parent[ra] = rb; count--; }
        }
        return count;
    }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

int countComponents(int n, vector<vector<int>>& edges) {
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    };
    int count = n;
    for (auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra != rb) { parent[ra] = rb; count--; }
    }
    return count;
}

Explanation

Start by pretending every node is alone in its own little group, so the component count begins at n. Every time an edge genuinely glues two separate groups together, the number of groups drops by one. Union-find tracks these merges efficiently.

The parent array records, for each node, who its representative is. The find function walks up the parent chain to the root of a node's group, and along the way does parent[x] = parent[parent[x]] (path halving) to keep the trees flat and fast.

For each edge (a, b) we compare roots. If find(a) != find(b), the two endpoints were in different groups, so we link them with parent[ra] = rb and do count -= 1. If the roots are already equal, the edge is redundant and the count stays put.

Example: n = 5, edges [[0,1],[1,2],[3,4]]. Edge 0-1 merges (5→4), edge 1-2 merges (4→3), edge 3-4 merges (3→2). The leftover groups are {0,1,2} and {3,4}, so the answer is 2.

When all edges are processed, count is exactly the number of connected components.

Time: O((n + e) · α(n)) Space: O(n)