Union-Find answers "same set?" fast by combining two
independent tricks: union by rank, and path compression.
Weighted Union-Find keeps both and adds a number. Union-Find with Rollback asks a
question neither of those can answer at all: "undo the most recent union." Answering it costs something —
path compression rewires pointers for every node along a walked path, not just the two roots being merged,
so there's no cheap way to know everything a compressing find just touched well enough to put
it back. Rollback Union-Find drops path compression and keeps only union by rank, so every union changes
exactly one parent pointer and, at most, one rank value — a change small and precise enough to record on a
stack and reverse in O(1), any time, as many times as there are unions still on it.
That's not a niche trade. It's the standard building block behind offline dynamic
connectivity: given a sequence of edges that each become active for a known span of time (added at
some moment, removed at a later one, all known up front), answer "are x and y
connected?" at various points in time. The usual technique recurses over time itself — like a segment tree,
but over time ranges instead of array indices — pushing each edge into every time-range node whose span it
fully covers, unioning the edges active in a range before recursing into that range's children, and
undoing them on the way back out before moving to a sibling range. That recursion's
backtracking is exactly a stack: unions nest and unwind in strict last-in-first-out order, never skipping
around — which is exactly the discipline this structure's O(1) undo is built to match.
Same eight elements as Union-Find, 0 through
7. Click a node to select it as A (dashed border), click a second to select it
as B (solid border), then press Union to merge their sets — every real
merge is pushed onto the history stack below the graph. Press Undo to pop the most recent
entry off that stack and revert exactly the pointer (and, if it changed, the rank) that union touched.
Press Find on a single selected node to walk up to its root — watch that the path never
gets rewritten, unlike Union-Find or
Weighted Union-Find: there is no path compression
here at all, the same trade Persistent Union-Find
makes for a different reason.
history stack — top block is what Undo reverts next
find(x) is the plain, uncompressed walk: follow parent pointers until one points at itself.
No second pass, no rewriting — the pointers a walk crosses are exactly as they were before the walk and
exactly as they'll be after it. That's slower than compressing Union-Find in the long run (see
Complexity), but it's the property that makes everything else on this page
possible: nothing a find does needs to be remembered in order to undo something later.
Union. union(x, y) finds both roots (by the plain walk above) and, if
they differ, attaches the shorter tree's root under the taller one's, by rank, exactly as plain
Union-Find does. Only two things ever change: one root's parent pointer, and — only when the two trees
had equal rank — the surviving root's rank, bumped up by one. Both are recorded together as a single
entry pushed onto a history stack before either write happens: which node got reattached, which root it
was attached to, and whether that root's rank was the one that got bumped. If the two elements are
already in the same set, nothing changes and nothing is pushed — there's nothing for an undo to reverse.
Undo. Pop the top entry off the history stack. Repoint the reattached node back to
itself — it's a root again — and, if that union had bumped a rank, subtract one back off it. That's the
entire operation: exactly the two writes the matching union made, run in reverse, nothing else touched.
Because a plain find never rewrites any pointer other than the two roots a union explicitly
attaches, no other node's state can have silently drifted out from under an undo — which is precisely the
property path compression would break (see Pitfalls).
Matches the demo above. Compare directly against plain
Union-Find's find: the only difference is the two-line compression pass at the end, which
this version simply never runs.
class RollbackDisjointSet {
#parent;
#rank;
#history; // stack of { child, parentRoot, rankBumped }
constructor(n) {
this.#parent = Array.from({ length: n }, (_, i) => i);
this.#rank = new Array(n).fill(0);
this.#history = [];
}
find(x) {
while (this.#parent[x] !== x) x = this.#parent[x]; // no compression, ever
return x;
}
// returns false if x and y were already in the same set (nothing pushed, nothing to undo)
union(x, y) {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
if (this.#rank[rx] < this.#rank[ry]) [rx, ry] = [ry, rx]; // ry is always the smaller-or-equal root
const rankBumped = this.#rank[rx] === this.#rank[ry];
this.#history.push({ child: ry, parentRoot: rx, rankBumped });
this.#parent[ry] = rx;
if (rankBumped) this.#rank[rx]++;
return true;
}
// reverts the most recently applied union; returns false if the history is empty
undo() {
if (this.#history.length === 0) return false;
const { child, parentRoot, rankBumped } = this.#history.pop();
this.#parent[child] = child;
if (rankBumped) this.#rank[parentRoot]--;
return true;
}
connected(x, y) {
return this.find(x) === this.find(y);
}
}Adding path compression back breaks undo — verified with real numbers, not just argued.
Take a 5-element structure and run union(0,1), union(2,3), then
union(0,2) — parent array becomes [0, 0, 0, 2, 4] (node 3's parent is 2, node
2's parent is root 0). Now add path compression back into find and call find(3):
the walk 3 → 2 → 0 compresses, and node 3's parent is rewritten straight to 0,
giving [0, 0, 0, 0, 4] — a change the history stack never recorded, because it happened inside
a find, not a union. Undo the most recent union — union(0, 2) — the
normal way: repoint node 2 back to itself. The result is [0, 0, 2, 0, 4], and it's wrong in
two directions at once: connected(3, 2) now reports false, even though that pair
was never part of the undone union and should still be together; connected(3, 0) reports
true, even though undoing union(0, 2) was specifically supposed to separate them.
Node 3 was silently repointed past the union being undone, and reverting only that union's own two writes
can't see it. This is why the reference implementation above never compresses — not a missing optimization,
a load-bearing omission.
Undo is strictly last-in-first-out. It can only revert the single most recent still-active union — there's no way to undo an earlier one while later ones remain on top of it, short of undoing everything down to that point and re-doing whatever should stay. That's a real limitation if a use case doesn't naturally nest that way, but it's exactly the shape offline dynamic connectivity's recurse-then-backtrack-over-time needs: unions applied on the way into a time range are always undone on the way back out, in the reverse order, before a sibling range starts — never out of order.
Undo has nothing to do with a general two-way split. It only reverses a union this
exact structure performed, using the bookkeeping that union itself pushed — it can't take an arbitrary
existing set and divide it into two arbitrary halves. Same limit
plain Union-Find names for merging in general: this structure adds one specific, narrow way back
(undo the last thing that happened), not an inverse for union in general.
Time: O(log n) worst case per find or union —
union by rank alone still bounds every tree's height at log₂ n, but without path compression
nothing ever shortens a path once it exists, so that bound is what every later find actually
pays, not just a rare worst case. Concretely: merging 64 elements in the worst order for union by rank
(pairing two equal-rank trees each round, so height climbs by exactly one every time) produces a tree where
every element's find costs up to 6 hops — log₂ 64 — forever. Plain
Union-Find's path compression would collapse that same tree
to a single hop per element after just one pass over all 64 — the gap this structure deliberately leaves
open in exchange for undo. Undo is O(1) — it reverses exactly the one or two
writes its matching union made, regardless of how large either set was. Space:
O(n) for the parent and rank arrays, plus O(u) for the history stack, where
u is the number of unions currently un-undone — entries are popped off as they're reverted, so
this tracks the depth of nested unions still standing, not the total number ever performed.
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.