Union-Find (also called a disjoint-set structure) tracks a collection of
elements split into non-overlapping groups, and answers exactly two questions fast: "are x
and y in the same group?" and "merge x's group and y's group
into one." No searching a group's members, no sorting, no comparisons between values at all — just
those two operations, both effectively O(1). That's a narrow contract, but it's exactly
the contract behind detecting cycles while building a graph edge-by-edge, and it's the standard
backbone of Kruskal's algorithm for minimum spanning trees
(add the cheapest edge that doesn't connect two things already connected — Union-Find is how you
check "already connected" without re-running a full traversal after every edge).
Eight elements, 0 through 7, start as eight separate one-element sets.
Click a node to select it (dashed border), click a second node to select it too (solid border), then
press Union to merge their sets — or select just one node and press Find
to see the path up to its set's representative ("root"). Press Step or
Run to walk through what happens. The line under a node shows its actual parent
pointer (a root points to itself); the chip strip below shows the real thing you probably care
about — the current partition into sets, independent of how the trees are shaped internally.
Each set is represented as a tree: every element points to a "parent," and the element sitting at
the root of the tree (pointing to itself) is that whole set's representative. find(x)
just walks parent pointers until it hits a root; two elements are in the same set exactly when
find gives them the same root. union(x, y) finds both roots and points one
at the other, merging the two trees into one.
Done naively, that degenerates fast — nothing stops the trees from growing into long chains, and a
long chain means an O(n) walk on every find. Two independent optimizations
fix that, and the demo above does both:
Union by rank. Track each root's rank (roughly, its tree's height) and
always attach the shorter tree under the taller one's root, never the other way
around. Attaching short-under-tall can't increase the taller tree's height, so height only ever grows
when two equal-rank trees merge — the same argument that bounds a balanced binary tree's height,
applied to attachment order instead of rotations. That alone caps every tree's height at
O(log n).
Path compression. While find(x) is already walking up to the root
anyway, make every node on that path point directly to the root before returning — not just
the node you started at. The next find on any of those nodes is then a single hop. This
is the same "pay down the cost while you're already there" idea as a queue's occasional compacting
pass, except here the payoff compounds: paths only ever get shorter, never longer, and after enough
finds nearly every element points straight at its root.
Neither optimization alone gets you all the way there — union by rank bounds height at
O(log n) on its own, and path compression alone still allows the occasional long walk.
Together, the amortized cost per operation is O(α(n)), where α is the inverse Ackermann
function — a function that grows so slowly it's under 5 for any input you could ever construct in
practice. Effectively constant, but not by accident: it falls out of the combination of both
tricks, not either one in isolation.
Matches the demo above: find does a first pass to locate the root, then a second pass
to repoint every node on the path directly at it (the standard two-pass "path compression," as
opposed to the recursive version that compresses on the way back up):
class DisjointSet {
#parent;
#rank;
constructor(n) {
this.#parent = Array.from({ length: n }, (_, i) => i);
this.#rank = new Array(n).fill(0);
}
find(x) {
let root = x;
while (this.#parent[root] !== root) root = this.#parent[root];
while (this.#parent[x] !== root) {
const next = this.#parent[x];
this.#parent[x] = root; // path compression
x = next;
}
return root;
}
union(x, y) {
const rx = this.find(x);
const ry = this.find(y);
if (rx === ry) return false; // already the same set
if (this.#rank[rx] < this.#rank[ry]) {
this.#parent[rx] = ry;
} else if (this.#rank[rx] > this.#rank[ry]) {
this.#parent[ry] = rx;
} else {
this.#parent[ry] = rx;
this.#rank[rx]++;
}
return true;
}
connected(x, y) {
return this.find(x) === this.find(y);
}
}It answers "same set?", not "who's in the set." find and
union never need to enumerate a set's members, so the structure doesn't track them —
only a root per set. If you need "list everyone in x's group," that has to be maintained
separately (e.g. a map from root to a members list, updated on every union), it isn't a free byproduct
of the structure above.
Merging is one-way. There's no split — once two sets are unioned,
undoing it means rebuilding from scratch (or keeping a full history of every union, which defeats most
of the point). Contrast with a linked list, where
removing a node is a normal, cheap operation the structure supports directly.
Path compression breaks a naive rank invariant, and the fix is to not worry about it. Union-by-rank's "rank" is meant to track height, but path compression can shorten a tree without updating the ranks of the nodes still above the compressed path — so after enough operations, rank is only an upper bound on height, not the exact value. This is fine: the amortized bound holds using rank as an upper bound, and "recompute exact heights after every compression" would cost more than the compression saved. It's a deliberately loose invariant, not a bug.
This is the undirected-graph analogue of the cycle check
topological sort's three-state DFS does for directed
graphs — but simpler, because undirected cycles don't need a third state. Process an
undirected graph's edges one at a time: before adding edge (x, y), check
connected(x, y). If it's already true, that edge would close a cycle — skip it (or flag
it) instead of unioning. If it's false, union them and move on. No DFS, no recursion stack, just this
structure — which is exactly the check Kruskal's algorithm runs
on every candidate edge while building a minimum spanning tree.
Extending "same set?" to "what's the difference?" If every union also carries a known numeric relationship between the two elements — not just "these are connected" but "y is exactly 5 more than x" — one extra number per node, updated carefully during path compression, turns this into Weighted Union-Find, which can also detect when a new constraint contradicts what earlier ones already imply.
Extending "merging is one-way" to "the most recent merge can be undone." Path
compression is exactly what stands in the way — it rewires pointers for nodes a union never directly
touched, so there's no cheap record of everything a compressing find just changed. Give up
path compression (keep only union by rank) and every union becomes a single, precisely reversible pointer
change, cheap enough to record on a stack: Union-Find
with Rollback.
Extending "undo the last merge" to "query any merge, ever." The same give-up-compression trick that makes rollback's undo cheap also makes every node's parent pointer change at most once, ever — which is enough to keep every past state queryable forever instead of just the single most recent one: Persistent Union-Find.
Extending "same set?" to a question about a different structure entirely. Run one DFS over a rooted tree and union each node into its parent's set the instant every child has returned — compression stays fully safe here, since nothing about this use ever needs to ask about the past — and a whole fixed batch of "what's the lowest common ancestor of these two nodes?" queries all get answered in that single pass, no per-query tree walk needed: Offline Lowest Common Ancestor (Tarjan's Algorithm).
Extending "which set is this in" to "what does this set actually contain." None of
the above ever look past the parent pointers themselves — but a real union frequently needs to merge
whatever each side is carrying too (a list of members, a running count, a set of colors seen). Always
copying the smaller side's data into the larger, never the reverse, bounds every element's total number
of moves to O(log n) across an entire sequence of unions, however it's ordered:
Small-to-Large Merging.
Recording the merges themselves, not just their end result. Run
Kruskal's algorithm's own sorted-edge scan, but every time
its cycle check accepts an edge, build a new tree node out of the union instead of only updating a
parent pointer — the resulting 2n - 1-node tree turns "what's the smallest possible
maximum edge weight on some path between these two nodes?" into a single lowest common ancestor
lookup, answered for any pair after one O(E log E) build:
Kruskal's Reconstruction Tree.
Time: with both union by rank and path compression, O(α(n)) amortized
per find or union — effectively constant. With only one optimization (or
neither), individual operations degrade toward O(log n) or O(n) in the worst
case, since nothing then stops a tree from becoming a long chain. Space:
O(n) — one parent slot and one rank slot per element, same as an
array-backed structure, no per-element pointers beyond
the single parent link.
This site's guide, Choosing a Union-Find Variant, compares this entry against the other three Disjoint Set structures that extend the same core contract side by side.