Connected Components (Union-Find)

Signal

"Count groups of nodes that end up merged together by a stream of edges" is the signature use case for a Disjoint Set Union (union-find) — you don't need to traverse the graph at all, just merge sets as edges arrive.

Approach

Start with every node in its own set. For each edge, union the two endpoints' sets. At the end, the number of distinct set roots is the number of connected components. Path compression (flatten the tree on find) and union by rank/size (attach the smaller tree under the bigger one) together keep every operation close to O(1).

Skeleton

parent[i] = i, rank[i] = 0 for all i
def find(x): path-compress while walking up to the root
def union(x, y): attach the smaller-rank root under the bigger one
for (u, v) in edges: union(u, v)
return number of distinct find(i) values

Solution

def count_components(n: int, edges: list[list[int]]) -> int:
    parent = list(range(n))
    rank = [0] * n

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression (halving)
            x = parent[x]
        return x

    def union(x: int, y: int) -> None:
        rx, ry = find(x), find(y)
        if rx == ry:
            return
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1

    for u, v in edges:
        union(u, v)

    return len({find(i) for i in range(n)})

Complexity

O((n + E) · α(n)) time — α is the inverse Ackermann function, effectively constant, thanks to path compression + union by rank. O(n) space.

Pitfalls

• Skipping path compression (or union by rank) still gives a correct answer but can degrade to O(n) per find on an adversarial edge order — both optimizations together are what makes DSU near-constant-time.
• Recomputing the final count with find(i) for every node (not caching parent[i] directly) — after all unions, some parent[i] may not point straight to the root unless you find it, since path compression only flattens paths that were actually walked.
• This same DSU scaffold is the building block for Redundant Connection and Kruskal's MST — recognize it as reusable, not a one-off.