Union-Find
Union-find answers one question fast: are these two things in the same group? Every element keeps a parent pointer, and following pointers leads to a root that stands for the whole group, so two elements are together exactly when their climbs end at the same root. Merging groups is one pointer change: hang one root under the other. Two small habits keep the climbs short. Hang the smaller tree under the larger, and after any climb, point everything you passed straight at the root. With both, a sequence of operations is effectively linear.
8 elements, each its own set: parent[i] = i marks a root, and every size is 1. The parent row is the whole structure. Following parents from any element leads to the root that names its set.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 19, with their answers.
find(0): which root does the climb reach?
Answer: 0. Follow parent pointers until one points at itself: 0.
find(1): which root does the climb reach?
Answer: 1. Follow parent pointers until one points at itself: 1.
Roots 0 (size 1) and 1 (size 1). Which goes under which?
Answer: 1 under 0. The smaller tree hangs under the larger, so no path gets longer than it must.
find(2): which root does the climb reach?
Answer: 2. Follow parent pointers until one points at itself: 2.
find(3): which root does the climb reach?
Answer: 3. Follow parent pointers until one points at itself: 3.
Roots 2 (size 1) and 3 (size 1). Which goes under which?
Answer: 3 under 2. The smaller tree hangs under the larger, so no path gets longer than it must.
find(1): which root does the climb reach?
Answer: 0. Follow parent pointers until one points at itself: 1 > 0.
find(3): which root does the climb reach?
Answer: 2. Follow parent pointers until one points at itself: 3 > 2.
Roots 0 (size 2) and 2 (size 2). Which goes under which?
Answer: 2 under 0. The smaller tree hangs under the larger, so no path gets longer than it must.
find(4): which root does the climb reach?
Answer: 4. Follow parent pointers until one points at itself: 4.
find(5): which root does the climb reach?
Answer: 5. Follow parent pointers until one points at itself: 5.
Roots 4 (size 1) and 5 (size 1). Which goes under which?
Answer: 5 under 4. The smaller tree hangs under the larger, so no path gets longer than it must.
find(3): which root does the climb reach?
Answer: 0. Follow parent pointers until one points at itself: 3 > 2 > 0.
find(5): which root does the climb reach?
Answer: 4. Follow parent pointers until one points at itself: 5 > 4.
Roots 0 (size 4) and 4 (size 2). Which goes under which?
Answer: 4 under 0. The smaller tree hangs under the larger, so no path gets longer than it must.
find(0): which root does the climb reach?
Answer: 0. Follow parent pointers until one points at itself: 0.
find(4): which root does the climb reach?
Answer: 0. Follow parent pointers until one points at itself: 4 > 0.
find(6): which root does the climb reach?
Answer: 6. Follow parent pointers until one points at itself: 6.
find(7): which root does the climb reach?
Answer: 7. Follow parent pointers until one points at itself: 7.
How it runs, step by step
8 elements, each its own set: parent[i] = i marks a root, and every size is 1. The parent row is the whole structure. Following parents from any element leads to the root that names its set.
8 singleton sets.
find(0): parent[0] = 0, so 0 is a root already. Its set is 0.
find 0 reaches root 0 after 0 steps.
find(1): parent[1] = 1, so 1 is a root already. Its set is 1.
find 1 reaches root 1 after 0 steps.
Roots 0 (size 1) and 1 (size 1). Union by size hangs the smaller root under the larger: parent[1] = 0, and 0's size grows to 2. Sets left: 7.
Root 1 now points at 0. 7 sets remain.
find(2): parent[2] = 2, so 2 is a root already. Its set is 2.
find 2 reaches root 2 after 0 steps.
find(3): parent[3] = 3, so 3 is a root already. Its set is 3.
find 3 reaches root 3 after 0 steps.
Roots 2 (size 1) and 3 (size 1). Union by size hangs the smaller root under the larger: parent[3] = 2, and 2's size grows to 2. Sets left: 6.
Root 3 now points at 2. 6 sets remain.
find(1): climb the parents, 1 > 0. The climb ends at 0, whose parent is itself, so 0 names the set.
find 1 reaches root 0 after 1 steps.
find(3): climb the parents, 3 > 2. The climb ends at 2, whose parent is itself, so 2 names the set.
find 3 reaches root 2 after 1 steps.
Roots 0 (size 2) and 2 (size 2). Union by size hangs the smaller root under the larger: parent[2] = 0, and 0's size grows to 4. Sets left: 5.
Root 2 now points at 0. 5 sets remain.
find(4): parent[4] = 4, so 4 is a root already. Its set is 4.
find 4 reaches root 4 after 0 steps.
find(5): parent[5] = 5, so 5 is a root already. Its set is 5.
find 5 reaches root 5 after 0 steps.
Roots 4 (size 1) and 5 (size 1). Union by size hangs the smaller root under the larger: parent[5] = 4, and 4's size grows to 2. Sets left: 4.
Root 5 now points at 4. 4 sets remain.
find(3): climb the parents, 3 > 2 > 0. The climb ends at 0, whose parent is itself, so 0 names the set.
find 3 reaches root 0 after 2 steps.
Path compression: every element on that path now points straight at 0. The next find on any of them is one step. The sets did not change, only their shape.
Path compressed: 3, 2 now point at 0.
find(5): climb the parents, 5 > 4. The climb ends at 4, whose parent is itself, so 4 names the set.
find 5 reaches root 4 after 1 steps.
Roots 0 (size 4) and 4 (size 2). Union by size hangs the smaller root under the larger: parent[4] = 0, and 0's size grows to 6. Sets left: 3.
Root 4 now points at 0. 3 sets remain.
find(0): parent[0] = 0, so 0 is a root already. Its set is 0.
find 0 reaches root 0 after 0 steps.
find(4): climb the parents, 4 > 0. The climb ends at 0, whose parent is itself, so 0 names the set.
find 4 reaches root 0 after 1 steps.
Both climbs reach root 0, so 0 and 4 are in the same set.
Connected.
find(6): parent[6] = 6, so 6 is a root already. Its set is 6.
find 6 reaches root 6 after 0 steps.
find(7): parent[7] = 7, so 7 is a root already. Its set is 7.
find 7 reaches root 7 after 0 steps.
6 reaches 6 and 7 reaches 7, different roots, so they are in different sets.
Not connected.
3 sets remain and the longest path to a root is 2. Union by size keeps depth at most log n, and path compression keeps flattening, so a sequence of m operations costs about O(m alpha(n)), effectively linear.
3 sets, longest path 2.
Remember
- A root is an element whose parent is itself; find climbs to it and that root names the set.
- union by size: hang the smaller root under the larger, so depth stays at most log n.
- Path compression: after a climb, point every visited element straight at the root.
Topics covered
Where this is used
Graph algorithmsKruskal's minimum spanning tree
Kruskal sorts every edge by weight and walks the list, keeping an edge only when its two endpoints still belong to different components. That test is exactly the connected query, and the union that follows returns false precisely when the edge would close a cycle, so the cycle check and the merge are one call rather than a separate traversal per edge. The Boost Graph Library's kruskal_minimum_spanning_tree is written straight on top of boost::disjoint_sets for this reason.
CompilersType inference in compilers
Hindley-Milner inference proceeds by unification: when two expressions are forced to have the same type, their type variables are merged into one equivalence class and the root of that class carries whatever concrete type has been pinned down so far. rustc does this with the ena crate, a union-find table pulled out of the compiler and published on its own. Inference also has to explore and back out, so that table is built around snapshots and rollback, which is the one case union-find handles badly and which decides how it is implemented.
Computer visionConnected-component labeling
The two-pass labeling behind OpenCV's connectedComponents gives each foreground pixel a provisional label copied from its already-scanned neighbours, and when two different labels turn out to touch it unions them instead of repainting anything. The second pass rewrites every provisional label to the root of its set, so a shape first discovered as four disconnected fragments comes out as one component. Without union-find the scan would have to go back and relabel every pixel it had already visited each time two fragments met.
SciencePercolation and cluster labeling
Percolation studies ask whether an open path runs from the top of a lattice to the bottom as sites are opened one at a time. Adding two virtual nodes, one joined to the top row and one to the bottom row, collapses that whole question into a single connected query between them, and opening a site is just a union with each open neighbour. That is how a grid of millions of sites is re-checked after every single change instead of being rescanned. When the lattice is fixed rather than growing, the Hoshen-Kopelman algorithm does the static version of the same job, labeling every cluster in one raster scan and unioning two labels wherever already-scanned neighbours turn out to touch.
Why it works this way
Why keep union by size when path compression already flattens the tree?
Path compression only shortens the paths you actually walked, and only once a find has walked them, so a run of unions with no finds in between can still build a long chain. Each habit on its own is worth about O(log n) per operation: union by size bounds the height outright, path compression pays for itself across a run of finds. Together they drop to the inverse Ackermann bound, which is a different curve rather than a constant-factor tidy-up. Union by rank stores an upper bound on height instead of a count of elements and behaves the same way, so pick one and stay consistent, because mixing a rank array with size comparisons gives you neither guarantee.
parent[x] is not the set id, find(x) is
Once elements have been merged, only the root's entries mean anything: size[] is stale for every non-root, and parent[] may still point at some middle node that no find has compressed yet. Two bugs follow from forgetting that. Writing parent[b] = a inside union instead of parent[find(b)] = find(a) moves only b's own subtree into a's set and quietly leaves the rest of b's set behind, and if a happens to sit under b it closes a cycle that makes find spin forever. Grouping the finished results by parent[i] rather than find(i) splits one set across several buckets; counting components is the one safe exception, since the number of i with parent[i] == i is exactly the number of roots.
Undoing a union is much harder than doing one
A merge is a single pointer write, so it looks trivially reversible, but the find that preceded it rewrote an unknown number of other parents on the way up and kept no record of what they were. The usual answer is DSU with rollback: drop path compression, keep union by size alone, and push the attached root and the old size onto a stack so each undo is one pop. That costs O(log n) per operation instead of near constant, and it is what algorithms that explore and backtrack use, from offline dynamic connectivity to the unification tables inside a type checker.
alpha(n) is not a polite way of writing log n
alpha is the inverse Ackermann function, and it is at most 4 for every n far beyond anything you could store, so treating the cost as constant is fair in practice. Two caveats still matter. The bound is amortized, so a single find can walk a long path before it flattens it, which shows up as jitter rather than a slow average. And it is not a gap waiting to be closed: Fredman and Saks proved a matching lower bound, so no structure of this kind does better.
Read more
- Disjoint-set data structureWikipedia
- Disjoint set unioncp-algorithms
- Union-FindSedgewick and Wayne · algs4.cs.princeton.edu
- Ackermann functionWikipedia
- Disjoint set unionUSACO Guide