Track which items belong to the same group, and merge groups instantly. Two small optimisations take it from linear to effectively constant time — and Kruskal's MST algorithm depends on it entirely.
Controls
Forest of Sets
step 0
parent[] array
Insight
Each set is a tree; the root is the set's representative. Find walks to the root, Union links one root under another.
groups8
max depth1
last find steps–
Complexity
With both optsO(α(n))
No optimisationsO(n)
SpaceO(n)
Union-Find (Disjoint Set)
Two optimisations that turn linear into effectively constant.
Quick Context
Union-Find maintains a collection of non-overlapping sets and supports two operations: find(x) — which set does x belong to? — and union(a, b) — merge the two sets containing a and b.
The Structure
Each set is stored as a tree, with every element pointing to a parent. The root represents the whole set. Two elements are in the same set exactly when they have the same root.
Union is therefore trivial: point one root at the other. All the difficulty is in keeping find fast, because it must walk to the root.
Optimisation 1: Union by Rank
Naively linking roots can build a long chain — press Build a bad chain with both optimisations off to see one. Depth grows to n and every find becomes O(n).
Union by rank always attaches the shorter tree under the taller one. The result never gets deeper than necessary, keeping depth at O(log n). Toggle the checkbox and rebuild the chain to compare.
Optimisation 2: Path Compression
When find(x) walks to the root, it already knows the answer for every node along the way — so it re-points them all directly at the root on the way back.
Press Find on a deep node with compression on and watch the tree flatten in a single operation. Each find makes all subsequent finds cheaper, so the cost is amortised away.
The Famous Complexity
With both optimisations, m operations on n elements cost O(m · α(n)), where α is the inverse Ackermann function. It grows so slowly that for any n that fits in the observable universe, α(n) < 5.
It is not technically constant, but it is constant for every practical purpose — one of the most striking results in data-structure analysis.
Where It Is Used
Kruskal's MST — sort edges, add one if its endpoints are in different sets. Union-Find is what makes the cycle check fast.
Connected components — in a graph, an image (flood fill), or a network.
Percolation and clustering — does a path exist from top to bottom?
Account or record merging — treating "these two IDs are the same person" as a union.
Interactive Exploration Guide
Union a few pairs and watch separate trees form. The group counter drops by one per successful merge.
Union two elements already in the same set. Nothing changes — and that check is exactly how Kruskal avoids creating a cycle.
Turn off both optimisations and press Build a bad chain. Depth grows linearly and finds get slow.
Turn path compression back on and run Find on the deepest node. The tree flattens in one step.
Compare max depth with rank on and off. Union by rank prevents the tall trees; compression fixes the ones already made.
Key Takeaway
Union-Find answers "same group?" and "merge groups" in effectively constant time, using union by rank to keep trees shallow and path compression to flatten them on the way. It is the structure that makes Kruskal's algorithm and fast connected-component queries possible.
Cheat sheet
Union-Find (Disjoint Set)
Track which items belong to the same group, and merge groups instantly. Two small optimisations take it from linear to effectively constant time — and Kruskal's MST algorithm depends on it entirely.