Patterns/Part II - Linked Structures/Persistent Union-Find

Pattern Reference

Persistent Union-Find

"Union-find with rollback capability for offline queries."

Loading...

Deep Dive Tutorial

Key constraint: path compression breaks rollback because it modifies many parent pointers. Use union-by-rank only (no path compression) — O(log n) per find instead of nearly O(1), but supports rollback. Each union operation modifies at most 2 values; log these on a stack. To rollback k operations: pop k entries from stack and restore parent/rank. DSU on a segment tree (each edge active during an interval) gives offline dynamic connectivity in O(n log²n).

DSU with rollback
class RollbackDSU {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.history = []; // stack of [node, oldParent, oldRank]
    }

    find(x) {
        while (this.parent[x] !== x) x = this.parent[x]; // no path compression!
        return x;
    }

    unite(x, y) {
        x = this.find(x); y = this.find(y);
        if (x === y) { this.history.push(null); return false; }
        if (this.rank[x] < this.rank[y]) [x, y] = [y, x];
        // Log changes before making them
        this.history.push([y, this.parent[y], x, this.rank[x]]);
        this.parent[y] = x;
        if (this.rank[x] === this.rank[y]) this.rank[x]++;
        return true;
    }

    rollback() {
        const entry = this.history.pop();
        if (entry) {
            const [y, oldParentY, x, oldRankX] = entry;
            this.parent[y] = oldParentY;
            this.rank[x] = oldRankX;
        }
    }

    save() { return this.history.length; } // checkpoint
    rollbackTo(checkpoint) {
        while (this.history.length > checkpoint) this.rollback();
    }
}

// DSU on segment tree for offline dynamic connectivity
// Each edge [u, v, from_time, to_time] → add to interval [from, to) in seg tree
// DFS seg tree: at leaf = query; at node = unite, recurse children, rollback

Worked Problems

1
Number of Islands II
Hard
Solve ↗
2
Checking Existence of Edge Length Limited Paths
Hard
Solve ↗
3
Offline Dynamic Connectivity (segment tree + rollback DSU)
Hard
Solve ↗
⏪
DSU with rollback key restriction: No path compression — must use find by following parent pointers (O(log n) per find). Path compression would modify many parent pointers and make rollback expensive.

Offline dynamic connectivity: When edges have time intervals [add_time, remove_time], build a segment tree on time. Insert edge into segment tree at its time interval. DFS the segment tree: unite at each node, recurse children, rollback on exit.

Complexity: O(n log n × log n) = O(n log²n) for offline dynamic connectivity with DSU on segment tree.
← All Patterns