Number of Connected Components in an Undirected Graph

mediumTests passed 2026-11-11v1.0.0
TC: O(V + E * a(V))|SC: O(V)
GraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Disjoint Set Union (DSU) with path compression + union-by-rank/size: initialize `components = n`, decrement `components` on every successful union between distinct roots.

2. Complexity Bounds & Proof

Inverse Ackermann amortized union/find runs effectively constant per edge; space holds only `parent` and `rank` arrays.

3. Minimal Idiomatic Code

def countComponents(n: int, edges: list[list[int]]) -> int:
    parent = list(range(n))
    rank = [1] * n
    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    comp = n
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            if rank[ru] < rank[rv]:
                ru, rv = rv, ru
            parent[rv] = ru
            rank[ru] += rank[rv]
            comp -= 1
    return comp

4. Failure Modes & Interview Follow-ups

Pitfalls:- Counting roots via an extra final pass vs decrementing `components` inline during union. - Forgetting `find(x)` path halving/compression can degrade skewed trees to O(V) per query.
Follow-ups:- Redundant Connection asks which exact edge first triggers `find(u) == find(v)`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Graph Valid Tree (O(N * a(N)))Number of Islands (O(M * N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.