Number of connected components

Count the separate groups in an undirected graph of n nodes. Start with n groups and let union-find merge them edge by edge.

The idea

Before looking at any edge, each node is a component on its own, so there are n. An edge either joins two different components, which merges them and lowers the count by exactly one, or it joins two nodes that are already connected, which changes nothing. Union-find tells the two cases apart: compare the roots of both ends.

Code

public int CountComponents(int n, int[][] edges) {
    var parent = new int[n];
    var rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int count = n; // every node starts as its own component
    foreach (var e in edges) {
        int ra = Find(parent, e[0]), rb = Find(parent, e[1]);
        if (ra == rb) continue; // already in the same component
        if (rank[ra] < rank[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra; // hang the shorter tree under the taller one
        if (rank[ra] == rank[rb]) rank[ra]++;
        count--; // two components became one
    }
    return count;
}

static int Find(int[] parent, int x) {
    if (parent[x] != x)
        parent[x] = Find(parent, parent[x]); // path compression: point x straight at its root
    return parent[x];
}

Tips

• Isolated nodes still count: node 6 in the default example has no edges and stays a component of its own.
• The answer is also the number of nodes that are still their own root at the end (the highlighted cells in the parent row).
• DFS or BFS from every unvisited node gives the same count in O(n + E); union-find shines when edges arrive one at a time.

In the .NET library

C# tuple swap (ra, rb) = (rb, ra) keeps union by rank to one line, with no temporary variable.