Number of Connected Components

Number of Connected Components is the classic introduction to union-find (also called disjoint set union). It teaches a structure that answers "are these two things in the same group?" almost instantly, and it shows up the moment a problem talks about connectivity.

The slow way first

You could build an adjacency list and run a DFS or BFS from every unvisited vertex, counting how many times you have to start a fresh search. That works and is O(n + e), but it means managing a visited set, a stack or queue, and the whole traversal.

Union-find gives the same answer with far less bookkeeping. Instead of walking the graph, we just merge groups as we read each edge.

The idea: union every edge, count the roots

Give each vertex its own group, so we start with n components. Then for each edge [a, b], union the two endpoints: if they are in different groups, merge them and drop the component count by one. If they were already connected, the edge changes nothing.

Each vertex points to a parent; following parents until one points to itself gives the root of its group. Two vertices are connected exactly when they share a root. After all edges, the number of distinct roots is the answer.

Walk through it

Step through the animation. We start with count = 5. Edge [0, 1] merges 0 and 1 → count 4. Edge [1, 2] finds 1’s root is now 0 and merges 2 in → count 3. Edge [3, 4] merges a separate pair → count 2. The roots left are 0 and 3, so the answer is 2.

Pseudocode

parent[i] = i for every vertex      # each vertex is its own root
count = n                           # n separate components
 
find(x): follow parent[x] until a vertex points to itself; return it
 
for each edge [a, b]:
    ra, rb = find(a), find(b)
    if ra != rb:                    # different groups
        parent[rb] = ra            # merge: attach one root under the other
        count -= 1                 # one fewer component
return count

The Python solution

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

• parent = list(range(n)) makes every vertex its own root, so we begin with n components.
• find(x) walks up the parent chain until it reaches a vertex that points to itself — that is the root of the group.
• For each edge we compute both roots with find(a) and find(b).
• if ra != rb is the key check: the endpoints are in different groups, so this edge truly connects two components.
• parent[rb] = ra merges them by hanging one root under the other, and count -= 1 records that two groups became one.
• An edge whose endpoints already share a root is skipped — it adds no new connection.

Complexity

The parent array uses O(n) space. With path compression and union by rank, each find/union is effectively constant time (the inverse-Ackermann factor α(n) is below 5 for any realistic input), so the whole pass is essentially O(n + e).

When this pattern shows up

Practice