Union-find

Union-find answers one question — are these two nodes in the same group — and supports one update: merge two groups. That is a narrower interface than a traversal, and the narrowness is what buys the speed. Each operation costs effectively constant time, so a million merges and queries cost about a million steps.

Each group is a tree, each node stores a parent, and the root is the group's name. find(x) walks to the root; two nodes are in the same group when their roots match.

The naive version degrades to a linked list

Merging by pointing one root at the other, with no care about which, builds chains. Union 2 into 1, then 3 into 2, then 4 into 3, and find(4) walks three hops. Do it n times and a single find costs O(n) — the structure has become a linked list with extra steps.

Two fixes together fix it completely.

Union by rank and path compression

Union by rank attaches the shorter tree under the taller one, so the height grows only when two equal-height trees merge. That alone bounds find at O(log n).

Path compression repoints every node on the walked path directly at the root, so the next find on any of them is one hop. Finding the root takes one pass and rewiring takes a second pass down the same nodes, so the constant doubles and the asymptotics do not move.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n                     # number of groups

    def find(self, x):
        root = x
        while self.parent[root] != root:                   # pass 1: find the root
            root = self.parent[root]
        while self.parent[x] != root:                      # pass 2: rewire the path
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                   # already together
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

A union-find forest before and after path compression: find(4) walks three parent hops, then repoints every node it passed straight at the root100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Tarjan's result is that m operations on n elements cost O(m · α(n)), where α is the inverse Ackermann function. It grows so slowly that α(n) ≤ 4 for any n you could store in memory, so the honest summary is effectively constant amortised time — not literally O(1), and never more than a small constant in practice. The proof is not something to derive at a whiteboard; quoting the result and its practical size is the expected answer.

When to reach for it instead of a traversal

Both union-find and a traversal can tell you whether two nodes are connected. On a fixed graph, a single traversal labelling every node with its component id is simpler and equally fast — do that.

The difference appears when edges arrive over time. With m queries interleaved with edge insertions, the traversal has to rerun after each change: O(m(V + E)). Union-find absorbs each edge in near-constant time and answers each query the same way. At V = 10⁵, E = 2 × 10⁵ and m = 10⁵ queries, rerunning traversals is about 10⁵ × 3 × 10⁵ = 3 × 10¹⁰ steps — minutes at 10⁸ operations per second. Union-find absorbs the same workload in V + E + m ≈ 4 × 10⁵ near-constant steps. That is the whole case for the structure: incremental connectivity.

Know what it cannot do. It has no notion of distance, so it will never tell you how far apart two nodes are — that is BFS. It has no path, only membership. And it cannot un-merge: removing an edge means rebuilding from scratch, which is why problems that delete edges are usually solved by processing time backwards, so deletions become insertions.

Two things you get for free

Counting components. Start the counter at V and decrement on every union that actually merged. The return False branch above is the one that does not count. After processing all edges, count is the number of connected components, at no extra cost.

Cycle detection in an undirected graph. If find(u) == find(v) before you union them, u and v were already connected, so this edge closes a cycle:

def has_cycle(n, edges):
    dsu = DSU(n)
    return any(not dsu.union(u, v) for u, v in edges)

This is exactly the test inside Kruskal's minimum spanning tree: sort edges by weight, take each one whose endpoints are in different groups, skip the rest. The skipped ones are the cycle-closing edges. For the directed case the answer is different and union-find does not apply — see cycles and topological order, where direction means a three-colour DFS instead.

In an interview

Lead with the interface, not the implementation: "union-find gives me same-group queries and merges in effectively constant amortised time, α(n) ≤ 4." Then justify choosing it over a traversal in one sentence — "the edges arrive one at a time and I am asked between arrivals, so a traversal would rerun."

Write union by rank and path compression together. Writing one without the other is a half-answer, and an interviewer who is paying attention will ask for the worst case, which is O(log n) rather than the near-constant you claimed.

The mistake that loses points: using union-find on a static graph where one traversal would do, then having no answer when asked why. The structure is not a general-purpose replacement for BFS; it trades away distance and paths for cheap incremental merges.

Check yourself

A graph is fixed, and you are asked once whether two nodes are connected. Union-find or BFS?

BFS, or one traversal that labels every node with a component id. Both are O(V + E) here and the traversal is less code. Union-find earns its place when the edges keep changing between queries.

You ship union by rank but forget path compression, on 10⁶ operations over 10⁶ elements. What is the worst case, how far is it from what you claimed, and will your tests catch it?

Rank alone bounds a find at O(log n): log₂ 10⁶ ≈ 20, so 10⁶ operations cost about 2 × 10⁷ steps. With compression the bound is α(n) ≤ 4, so about 4 × 10⁶ — roughly five times cheaper. Your tests will not catch it: at 10⁸ operations per second both finish in under a second. What you have broken is the claim, not the run — you said "effectively constant amortised" and shipped logarithmic, and the interviewer who asks for the worst case gets O(log n).

You process 10 undirected edges over 8 nodes and union returns False three times. How many components remain, and what else does that number tell you?

Seven unions succeeded, so 8 − 7 = 1 component. The three failures are edges whose endpoints were already connected — each closes a cycle, so the graph has cycles and is not a tree.