This site's Disjoint Set category holds ten entries, but only
four of them answer the same core contract — "are x and y in the same
group?" and "merge their groups" — with something extra layered on top: Union-Find, Weighted Union-Find, Union-Find with Rollback, and Persistent Union-Find. Five more use
Union-Find as a building block for a different underlying question rather than extending its
contract at all: Offline Lowest
Common Ancestor runs one DFS pass over a fixed tree and unions nodes into their parent's set to
answer a batch of "what's the lowest common ancestor of these two nodes?" queries — its own opening
line calls itself "the first one that isn't a variant of the structure itself." Small-to-Large Merging answers a different
question again: not "how do I merge sets faster," but "how do I also merge whatever data is
attached to each set — a member list, a running count — without that blowing up past
O(n log n) total." Kruskal's Reconstruction Tree answers a
third: not "same set?" at all, but "what's the smallest possible maximum edge weight on some path
between these two nodes?" — replaying Kruskal's own sorted-edge merges as tree nodes instead of
parent-pointer updates. Offline Dynamic
Connectivity answers a fourth: given a whole batch of edges each active only during a known span
of time, and a whole batch of connectivity queries at various times, answer every query in one pass —
by recursing a segment tree over time itself, built on top of Union-Find with Rollback specifically
(more on that below). Randomized Kruskal's Maze
Generation is a fifth, and the only one that never answers a question at all once it's done: the
same-set check runs purely to keep a randomly-ordered grid-graph spanning tree free of cycles while
it's being built, and once every candidate wall has been tested the structure is thrown away — a
finished maze remembers nothing about how it was built. All five are genuinely useful, but none is a
choice you make instead of one of the four below — they sit on top of whichever one you'd have picked
anyway (all five source pages use plain Union-Find or Union-Find with Rollback underneath). The
tenth, Partition Refinement, is a different
kind of exception again — not built on Union-Find at all, sharing no code or implementation idea with
it. It answers the literal opposite question: instead of merging groups together, it only ever splits
an existing group apart, and can never merge two groups back. It sits in this category for topical
proximity, not because it competes for the same job. This guide only compares the four that actually
compete for the same job.
Every prior guide on this site collapses to one decision tree, because its entries only ever add one thing at a time. Union-Find's four variants don't work that way: does a union carry a numeric relationship you need to query and does anything need to reach into the structure's past are separate questions that happen to each have exactly one entry answering "yes." Weighted Union-Find's own Pitfalls section says this directly: "Weights and rollback are separate extensions, not stackable for free... Combining both ideas in one structure is possible in principle but isn't free: it needs care neither page's implementation provides on its own." So treat the two questions below as independent, not as branches of a single tree — if the answer to both is "yes," none of this site's four pages is a drop-in answer by itself, and building both extensions into one structure is real work this guide doesn't hand you for free.
Plain Union-Find only ever records "these two are now in the same group" — nothing about how
they're related, and no way to detect when a new fact contradicts an earlier one. Weighted Union-Find answers a sharper question:
every union carries a known offset — "y is exactly w more than
x" — and the structure derives implied relationships between elements that were never
directly unioned at all. Its own worked example: union(0, 1, 3) then union(1, 2, 2) never states
anything about element 2 relative to element 0 directly, but find(2) already returns
offset +5 from root 0 with no extra bookkeeping — and a third union(0, 2, 6) is caught
as a contradiction (the structure already knows the answer is 5, not 6) in exactly the same two
find calls every other query costs. If nothing in the workload needs relationships
between elements — just "same group, yes or no" — this entire axis is skippable and the deciding
question is only the one below.
If the answer is no, stop here — plain Union-Find
(or Weighted Union-Find, if the question
above was yes) is both the cheapest and the simplest option; nothing below beats
O(α(n)) amortized. If the answer is yes, the deciding question is how much of
the past needs to be reachable, and in what order:
Only the single most recently applied union, undone in strict last-in-first-out
order. Union-Find with Rollback
drops path compression — keeping only union by rank — so every union changes exactly one parent
pointer (and, at most, one rank value), small and precise enough to push onto a history stack and
reverse in O(1). That's the exact shape Offline Dynamic
Connectivity needs: recursing over time ranges the way a segment tree recurses over
array indices, unioning edges active in a range on the way in and undoing them on the way back out
before a sibling range starts — recursion's own backtracking is already a stack, so undo only ever
needs to reverse the single most recent entry. Giving up compression isn't free: its own Complexity section measures the
gap directly — merging 64 elements in the worst order for union by rank produces a tree where
every find costs up to 6 hops (log₂ 64) forever, where plain Union-Find's
path compression would have collapsed that same tree to a single hop per element after just one
pass over all 64 elements.
Any past version, queried in any order, without touching the current live state.
Persistent Union-Find answers "were
x and y connected as of version 7?" directly, for any past version, as
many times as needed, in whatever order the questions arrive — no undoing, no winding. Rollback
could only answer the same sequence of questions by winding through undo one union at a time in
strict order; asking about version 7 and then version 40 means undoing all the way down to 7, then
redoing back up to 40. Persistent Union-Find gets there because a node's parent pointer changes at
most once, ever under union by rank alone — so full history costs close to nothing extra,
not the O(log n)-per-version blowup a general persistent structure pays. Its own Complexity section backs that with
a real stress test, not just the argument: 3,000 random unions over 500 elements produced exactly
499 successful merges (a spanning tree's worth, the most any 500-element disjoint-set can accept)
and exactly 499 permanent parent-change records — a clean one-to-one match. One honest limit shared
with rollback: this is partial persistence, not full — a new union always extends the
current latest version, and there's no branching a second future off an older one without touching
everything built since. Same boundary rollback draws around its own strictly-LIFO undo, just for a
different reason.
| Entry | Adds | Time | Space | Reach for it when |
|---|---|---|---|---|
| Union-Find | — (baseline) | O(α(n)) amortized | O(n) | just "same set?" and "merge," nothing else |
| Weighted Union-Find | numeric offset per union, contradiction detection | O(α(n)) amortized | O(n) | unions carry a known relationship you need to query or check for consistency |
| Union-Find with Rollback | undo the single most recent union | O(log n) worst case, undo O(1) | O(n) + O(u) history stack | undo is strictly LIFO-nested (e.g. Offline Dynamic Connectivity) |
| Persistent Union-Find | query any past version | O(log n) per query | O(n) total, O(1) amortized per union | need "connected as of version v" for arbitrary v, in any order |