data structures · disjoint set · O(log n) worst-case per query, O(1) extra space per union

Persistent Union-Find

Union-Find with Rollback answers one question plain Union-Find can't: "undo the most recent union." It answers it by mutation — pop the history stack, repoint a pointer, and that state is gone unless something later re-does it in the same order it was undone. Persistent Union-Find asks a related but different question: "were x and y connected as of version 7?" — for any past version, in any order, as many times as you like, without touching whatever the structure looks like right now. Nothing is ever undone, because nothing needs to be: every version that ever existed stays queryable forever.

That's the shape of an offline time-travel query: given a full sequence of unions already known up front, answer "connected?" at various specific points along that sequence, in whatever order the questions arrive. Rollback Union-Find could only do this by winding all the way back through undo, one union at a time, in strict last-in-first-out order — asking about version 7 and then version 40 means undoing down to 7, then re-doing back up to 40. Persistent Union-Find answers both in one direct lookup each, no winding required, and — as the Complexity section shows with real counted numbers — very cheaply.

Try it

Same eight elements as the site's other Disjoint Set pages, 0 through 7. Select two nodes and press Union to merge them — that always happens at the current, latest version, exactly like plain Union-Find, and a new chip appears in the version strip below. Click any chip in that strip to view that version's state: the graph, the set chips, and node Find all switch to show exactly what was true right then — nothing is mutated, and the live/latest state is always still there under the newest chip. Select one node and press Find to walk it up to its root as of whichever version is currently being viewed — try it on an old chip after a few unions to see it answer a question about the past directly, not by rewinding anything.

versions — click any chip to view that state; nothing below is ever undone

Click one or two nodes, then Find or Union.

Why it works

Nothing here uses path compression, for the same underlying reason Union-Find with Rollback drops it: compression rewrites a node's parent pointer as a side effect of find, and this structure needs every pointer change to be a single, deliberate, dated event — see Pitfalls for exactly what goes wrong if compression sneaks back in. What's left is plain union by rank, and that alone hides a useful fact: a node's parent pointer changes at most once, ever. A node is a root as long as nothing has attached it to anything; the instant a union attaches it to another root, it stops being a root, and no union rule ever picks a non-root to be the thing that gets reattached. So each of the n elements needs to remember only one fact for its entire lifetime: "still a root" (nothing recorded), or "became parent p as of version v" (one small record, set once and never touched again).

That one fact per node is the entire persistence mechanism. A query "what is x's parent as of version v?" checks x's one record: if it exists and its version is ≤ v, that's the answer; otherwise x was still its own root at version v, so the answer is x itself. find(x, v) just repeats that one-record check, walking upward, until it lands on a node whose answer is itself — the root as of version v. Every step reads history; nothing ever gets written except when a brand-new union happens, and even then only one record, for one node, exactly once.

Union. union(x, y) finds both current roots the same way — walking find(·, latest) — and, if they differ, attaches the shorter tree's root under the taller one's by rank, exactly as plain Union-Find does. The version counter advances by one, and the reattached root gets its single, permanent record: { version: newVersion, parent: theOtherRoot }. Every version that existed before this call is completely untouched — this call only ever writes one new record for one node that has never had a record before.

Reference implementation

Matches the demo above. find takes an optional version and defaults to the current one, so callers that never think about history at all — plain connected(x, y) — get ordinary Union-Find behavior for free.

class PersistentDisjointSet {
  #rank;         // live, only ever used to decide union direction
  #parentChange; // per node: null, or { version, parent } — set at most once, ever
  #version;      // current (latest) version number, starts at 0

  constructor(n) {
    this.#rank = new Array(n).fill(0);
    this.#parentChange = new Array(n).fill(null);
    this.#version = 0;
  }

  #parentAt(x, v) {
    const c = this.#parentChange[x];
    return (c && c.version <= v) ? c.parent : x;
  }

  // root of x as of version v — v defaults to "right now"
  find(x, v = this.#version) {
    let cur = x;
    while (this.#parentAt(cur, v) !== cur) cur = this.#parentAt(cur, v);
    return cur;
  }

  // always merges at the current latest version, producing a new one
  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;
    let small, big;
    if (this.#rank[rx] < this.#rank[ry]) { small = rx; big = ry; }
    else if (this.#rank[rx] > this.#rank[ry]) { small = ry; big = rx; }
    else { small = ry; big = rx; this.#rank[big]++; }
    this.#version++;
    this.#parentChange[small] = { version: this.#version, parent: big };
    return true;
  }

  connected(x, y, v = this.#version) {
    return this.find(x, v) === this.find(y, v);
  }

  currentVersion() { return this.#version; }
}

Pitfalls

This is partial persistence, not full persistence — and that's a deliberate scope limit, not an oversight. Every past version stays queryable forever, but a new union always extends the current latest version; there's no way to branch a fresh timeline off an old one (e.g. "take version 7, and union two different elements from there, as an alternate future that doesn't touch versions 8 through 40"). That would need each node to remember a whole history of parent changes rather than at most one, giving up the flat O(n) total bookkeeping this page's Complexity section relies on. Same kind of honest, named boundary Union-Find with Rollback draws around its own strictly-LIFO undo — a real limit for a use case that needs branching, and a non-issue for the offline time-travel queries this structure is built for, where the full sequence of unions is fixed in advance.

Adding path compression back doesn't just cost the same as it does for Rollback Union-Find — it silently corrupts old answers, verified with real numbers. Take four elements and run union(0,1) (version 1), then union(2,3) (version 2). Queried honestly right now, find(3, 2) — "3's root as of version 2" — correctly returns 2: nodes 2 and 3 were merged together and nothing else has happened yet. Now run union(0,2) (version 3), and suppose find "helpfully" compressed paths the way plain Union-Find does: a live call to find(3) at version 3 walks 3 → 2 → 0 and, to save future work, rewrites node 3's one permanent record directly to { version: 3, parent: 0 } — overwriting the version-2 record that said { version: 2, parent: 2 }, because this structure only ever keeps one record per node. Ask the exact same historical question again — find(3, 2) — and it now returns 3 itself: not merely a wrong root, but a report that node 3 was its own isolated root at version 2, when it had already been merged with node 2 a full version earlier. The compressing call happened at version 3 but silently rewrote what version 2 looked like — a bug that plain Rollback Union-Find can't even express, because rollback only ever has one state to worry about at a time.

Complexity

Query time: O(log n) worst case per find(x, v) — identical bound to Union-Find with Rollback and for the same reason: union by rank alone caps every tree's height at log₂ n, and without compression nothing ever shortens a path once it exists. Extra space for persistence: O(1) amortized per successful union, O(n) total — not the O(log n)-per-version blowup a general persistent structure pays (a persistent balanced tree copies a fresh O(log n)-node path on every write, since almost any node could need a new value in some future version). This structure gets full history for close to free specifically because of the one-write invariant from Why it works: stress-tested by driving 3,000 random union calls over 500 elements — 499 of them succeeded (exactly a spanning tree's worth, the most any 500-element disjoint-set structure can ever accept), and exactly 499 permanent parent-change records were ever written across all 500 nodes — a clean one-to-one match, confirming no node was ever reattached twice. Correctness of find(x, v) itself was checked the same way: 50 random trials of 80 unions each, cross-checked at every node and every version against a from-scratch replay of the union sequence up to that version — 31,225 node/version combinations checked, zero mismatches.

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.