Union-Find (Disjoint Set Union)

You have n items, each starting in its own group. Two operations: union(a, b) merges the groups containing a and b, and find(x) tells you which group x belongs to, so two items are connected exactly when find gives the same answer. Groups only merge; they never split.

This appears in network connectivity, grouping friends or accounts, image regions, and cycle detection in graphs. Connections arrive one at a time and you want an answer after each one.

Running BFS for every question costs O(n + m) each time. Keeping a group label on every item makes find O(1), but each merge must relabel a group. Union-find gets both operations close to constant time, at the price of supporting merges only.

Store each item's parent in an array. A root is its own parent. To find the group of x, follow parents up to the root. To union two groups, point one root at the other.

This is correct but can be slow. If you always attach the same way you can build a long chain, and find becomes O(n). Take six items and call union(0, 1), union(1, 2) and so on up to union(4, 5), each time pointing the first root at the second. The parent array becomes [1, 2, 3, 4, 5, 5]: 0 points to 1, 1 points to 2, and 5 is the root. That is a chain of height 5, and find(0) walks every link. Repeated finds turn quadratic: in the benchmark below, 10,000 items cost 99,990,000 parent hops.

The root is only a label, so never assume the representative is the smallest id. Two small tricks fix the speed problem.

Path compression makes later finds shorter by pointing nodes closer to the root as you pass them. The loop above uses the path-halving form: every node it visits is pointed at its grandparent, in one pass with no recursion. Full compression points every node straight at the root and is usually recursive, which can hit Python's default recursion limit of 1000 frames on a deep tree.

The diagram shows halving on the six-item chain. One find(0) rewrote two pointers and cut the height from 5 to 3; a second moved item 0 up to 4. Compression is lazy and only repairs paths you use.

Union by rank keeps trees shallow. Rank grows only when two trees of equal rank are joined, so a root of rank k has at least 2^k items and no rank exceeds floor(log2 n). Rank is an upper bound on height, because compression shrinks trees without touching ranks.

Union by rank alone guarantees O(log n) per find. With both tricks, m operations on n items cost O(m alpha(n)), so O(alpha(n)) amortised per operation, where alpha is the inverse Ackermann function. Tarjan proved this bound in 1975 and later showed it is tight, and Fredman and Saks showed in 1989 that no disjoint-set structure can beat it in the cell-probe model. alpha(n) is at most 4 for any n that could be written down in the physical universe.

Note the wording. Amortised means one find can still be slow. And O(alpha(n)) is not O(1); it just grows too slowly to notice.

I started with eight items, 0 to 7, and applied these unions with the class above. Each row shows whether the union changed anything, how many groups were left, and the parent array p and rank array r after the call.

In the third row, union(1, 3) finds roots 0 and 2. Both have rank 1, the tie goes to the first argument, so 2 goes under 0 and the rank of 0 rises to 2. Item 3 still points at 2, because nothing has searched for it yet.

Now find(0) == find(2) is True and find(0) == find(4) is False, since {0,1,2,3} and {4,5,6,7} are separate. union(3, 0) returned False: both finds reached root 0. That False is the signal used for cycle detection.

A last union(0, 4) joined two rank-2 roots, leaving [0,0,0,0,0,4,4,6]. Item 3 now points at 0, because the find inside union(3, 0) halved its path. Item 7 sits three links deep, the most union by rank allows for eight items (log2 8 = 3).

I counted parent-pointer hops inside find for four variants: naive (first root placed under the second), rank only, compression only, and both. In the chain workload, union(i, i + 1) runs for every i, then find(0) runs n times. In the random workload, each of n steps unions two random items and finds a third. This was Python 3.13 in a small sandbox, one run per row, so the seconds are rough; hop counts are exact for the seed.

The naive chain is the textbook failure: 10,000 finds, each walking 9,999 links. I skipped it at 100,000 items (about 10 billion hops). Random input still grew a naive tree 9,850 levels deep and took 28.1 seconds, about 120 times longer than 0.232 seconds with both tricks.

Either trick alone removes nearly all the damage. Combined, the random run did about half the hops of either alone, yet the clock barely moved, because per-call Python overhead dominates once trees are shallow. Running random unions with rank only until one group remained, 1,000 items ended at height 4 and 100,000 at height 7, below log2 n of 10 and 16.6.

A minimum spanning tree (MST) connects all nodes of a weighted graph with the least total edge weight. Kruskal's algorithm is greedy: sort edges by weight and add each edge unless it would form a cycle. Union-find answers the cycle question: if union returns False, the endpoints are already connected, so skip the edge.

I ran it on 5 nodes with edges (weight, a, b): (4,0,1) (8,0,2) (2,1,2) (6,1,3) (3,2,3) (5,3,4) (1,2,4). It chose 2-4 (1), 1-2 (2), 2-3 (3) and 0-1 (4), a total of 10, and skipped 3-4 (5), 1-3 (6) and 0-2 (8) because each would have closed a cycle. A spanning tree on V nodes has V - 1 edges, so the loop can stop at four. Sorting dominates, so Kruskal runs in O(E log E).

Connected components come almost free: union every edge and the groups counter is the component count.

Percolation is a physical example. Open cells of an N by N grid in random order, union each new cell with its open neighbours, and add two virtual nodes joined to the top and bottom rows. The grid percolates when they share a root. On a 100 by 100 grid over 20 seeds, the mean fraction of open cells at that moment was 0.5944 (range 0.5481 to 0.6196), and all 20 runs took 0.3 seconds. That is close to the site percolation threshold of about 0.5927 listed for the square lattice.

Union-find cannot undo a union, so it is wrong for problems where connections can be removed (those need other structures, such as offline tricks or link-cut trees). It also answers connectivity questions only; to list every member of a group you need extra bookkeeping. For a graph that never changes, one BFS or DFS pass labels components just as well.

Common bugs:

• Comparing p[a] == p[b] instead of find(a) == find(b). Items 1 and 3 in the trace shared a root but had different parents.
• Writing p[a] = b without finding roots first, which detaches a and its subtree and silently splits its group.
• Raising rank on every union instead of only on ties, which breaks the log n height bound.
• Labels that are strings or sparse ids. Map them to indexes, or keep parents in a dictionary.

Q: What are the time complexities of find and union?
A: With path compression and union by rank, O(alpha(n)) amortised per operation, where alpha is the inverse Ackermann function, at most 4 for any realistic n. Union by rank alone gives O(log n).

Q: Why does union by rank matter if you already compress paths?
A: Compression only repairs a path after it is walked, so the first find on a chain pays for the whole chain. Rank stops chains forming. In my chain test, compression alone left height 14; rank kept it at 1.

Q: How do you detect a cycle in an undirected graph?
A: Process edges; if both endpoints already share a root, the edge closes a cycle, otherwise union them. Directed graphs need DFS with colours instead.

Q: Walk me through Kruskal's algorithm.
A: Sort edges by weight, add each edge whose endpoints are in different groups, stop at V - 1 edges. O(E log E). The five-node example totalled 10.

Q: Path compression or path halving?
A: Compression points every node on the path at the root; halving points each at its grandparent in one iterative pass. Both reach O(alpha(n)) with union by rank.