#323MediumGraphs

Number of Connected Components in an Undirected Graph

The tell: Connectivity counting over a stream of edges — the classic union-find setup.

How you get there

1Start with n components, one per node.
2Each edge that joins two different components reduces the count by one.
3Path compression and union by size keep each operation near constant.

Solution

Python

def count_components(n: int, edges: list[list[int]]) -> int:
    parent = list(range(n))
    size = [1] * n
    components = n

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

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            continue
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
        components -= 1

    return components

Time: O(E · α(V))
Space: O(V)

What goes wrong

Skipping union by size degrades find toward O(n) on adversarial edge orders.

Test yourself on DSA Next: Pacific Atlantic Water Flow →