Union-Find with Rollback, in depth: undo logs, why compression breaks it, offline dynamic bipartiteness and backtracking

Why ordinary union-find cannot undo

A standard union-find stores a parent pointer per element. The root of each tree names the group. Two tricks make it fast: union by size (hang the smaller tree under the larger root) and path compression (during a find, point every visited node straight at the root). Together they give an amortised cost of O(α(n)) per operation, which is effectively constant.

Both tricks fight undo, for different reasons. Path compression rewrites pointers during a read. One find can change dozens of pointers, and you would have to log every one of them to restore the earlier shape. The log then grows with the number of finds, not the number of unions, and the undo becomes as expensive as the work it reverses.

Amortisation is the subtler problem. An amortised bound says that a long sequence of operations is cheap on average, because the expensive ones pay for the cheap ones that follow. Rollback breaks the accounting. An adversary can trigger one expensive operation, undo it, trigger it again, undo it again, and never let the structure collect the savings. Any structure you plan to roll back needs a worst-case bound per operation, not an amortised one.

So rollback union-find drops path compression and keeps union by size (or by rank). Union by size alone guarantees that a tree with height h has at least 2^h nodes, so no tree is taller than log₂ n. Every find costs O(log n) in the worst case, and every union changes a constant number of fields. Those few fields are what you log.

What goes on the undo log

Each successful union touches exactly one parent pointer (the smaller root now points at the larger root) and one size (the larger root's size grows). If you also maintain derived state, that changes too: a component counter drops by one, an aggregate at the root (sum, minimum, flag) absorbs the child's value. The undo record must hold enough to reverse each change. Two designs are common.

• Store the old values. Push tuples such as (array, index, old value) for every field you write. Undo pops and assigns. This is generic and hard to get wrong, which makes it a good choice when the root carries several aggregates.
• Store the operation. Push (child, root). Undo knows that the child was a root before, so it resets the child's parent to itself and subtracts the child's size from the root. This is smaller and faster, but only valid for state you can recompute exactly from the two endpoints. Subtraction works for sizes and sums; it does not work for a minimum, which needs the old value.

Unions that do nothing still need a record if callers take checkpoints by log length. If you skip them, a caller who unions three edges and then rolls back three records would also undo an earlier, unrelated union. Either push a no-op record or make checkpoints count only real changes, but pick one and test it.

A checkpoint is just the current log length. Rolling back to a checkpoint pops records until the log is that long again. Checkpoints nest naturally: a recursive search takes one on entry and restores it on exit, and inner levels cannot disturb outer ones because they only pop their own records.

Implementation with parity and component count

The implementation below keeps sizes, a component count, and a parity bit per node so that it can also answer whether each component is bipartite (two-colourable). The parity of a node is its colour relative to its parent, so a node's colour relative to its root is the XOR of parities along its path. Joining two different components with an edge forces the endpoints to different colours, which fixes the parity of the absorbed root. An edge inside one component whose endpoints already have the same colour closes an odd cycle; the counter bad records how many such edges are currently active.

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.parity = [0] * n      # colour of node relative to its parent
        self.comps = n
        self.bad = 0               # odd cycles seen so far
        self.log = []              # undo records

    def find(self, x):             # no path compression: reads never write
        p = 0
        while self.parent[x] != x:
            p ^= self.parity[x]
            x = self.parent[x]
        return x, p

    def union(self, a, b):
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        if ra == rb:
            if pa == pb:           # same colour on both ends: odd cycle
                self.bad += 1
                self.log.append(("odd",))
            else:
                self.log.append(("noop",))
            return
        if self.size[ra] < self.size[rb]:
            ra, rb, pa, pb = rb, ra, pb, pa
        self.log.append(("link", rb, ra))
        self.parent[rb] = ra
        self.parity[rb] = pa ^ pb ^ 1
        self.size[ra] += self.size[rb]
        self.comps -= 1

    def checkpoint(self):
        return len(self.log)

    def rollback(self, mark):
        while len(self.log) > mark:
            rec = self.log.pop()
            if rec[0] == "link":
                _, child, root = rec
                self.size[root] -= self.size[child]
                self.parent[child] = child
                self.parity[child] = 0
                self.comps += 1
            elif rec[0] == "odd":
                self.bad -= 1

Note what the undo does not touch. Nodes deeper in the absorbed tree still point at the child root, and their parities are relative to it, so restoring the child's own three fields restores the whole subtree. That is why the operation-style record is enough here: every write in union is reversible from (child, root) plus the record type.

Arbitrary deletions offline: a segment tree over time

Rollback only undoes the most recent union. Real workloads delete edges in arbitrary order. The standard bridge, sometimes called divide and conquer over time, works whenever every operation is known in advance (an offline problem).

1. Number the operations 0 to m-1. Each edge is alive over a half-open interval [added, removed); an edge never removed is alive until m.
2. Build a segment tree over [0, m). Insert each edge's interval: it lands on at most about 2 log₂ m canonical nodes, the same decomposition a range-update segment tree uses.
3. Walk the tree depth-first. On entering a node, take a checkpoint and union every edge stored there. At a leaf, the DSU holds exactly the edges alive at that moment, so answer that moment's query. On leaving, roll back to the checkpoint.

The walk visits nodes in stack order, so every undo is the most recent one, which is the only kind rollback supports. Each edge is unioned once per canonical node, so the total cost is O(m log m log n).

For bipartiteness there is a useful shortcut. Edges only accumulate as you descend, so if a node's unions already produced an odd cycle, every moment inside that node's range is non-bipartite. Answer them all as false and skip the subtree.

def solve(node, lo, hi):
    mark = dsu.checkpoint()
    for u, v in tree[node]:
        dsu.union(u, v)
    if dsu.bad > 0:                      # every time in [lo, hi) is non-bipartite
        for t in range(lo, hi):
            if ops[t][0] == "ask":
                answers[t] = False
    elif hi - lo == 1:
        if ops[lo][0] == "ask":
            answers[lo] = True
    else:
        mid = (lo + hi) // 2
        solve(2 * node, lo, mid)
        solve(2 * node + 1, mid, hi)
    dsu.rollback(mark)

If the segment tree is new to you, the segment tree article covers the interval decomposition this step relies on.

Worked example: bipartiteness under edits

Take five vertices and fourteen operations: add 0-1, add 1-2, ask, add 2-0, ask, delete 1-2, ask, add 2-3, add 3-4, ask, add 4-1, ask, delete 0-1, ask. The lifetimes are 0-1 on [0, 12), 1-2 on [1, 5), 2-0 on [3, 14), 2-3 on [7, 14), 3-4 on [8, 14) and 4-1 on [10, 14).

Running the code prints [True, False, True, True, False, True]. To check it, the same functions were run against a brute-force checker that rebuilds the graph and two-colours it with a search at every query, on 3,000 random operation sequences of up to 25 operations on up to 7 vertices. All 3,000 agreed.

Where rollback is used

The same structure appears outside competitive programming wherever a computation explores and backs out.

• Backtracking search. A solver that assigns variables and propagates equalities can keep equivalence classes in a rollback DSU, take a checkpoint per decision level, and roll back on conflict. Logic-programming engines have long kept an undo log of variable bindings (usually called a trail) for exactly this reason.
• Type inference and unification. Unifying two type variables is a union. A checker that tries one overload, fails, and tries another needs to discard the failed attempt's unions without rebuilding everything.
• Leave-one-out queries. To ask what the graph looks like without edge i, for every i, give each edge two lifetimes, [0, i) and [i+1, m), and run the offline walk. This answers all m questions in one pass instead of m separate rebuilds.
• Kruskal variants. Some minimum spanning tree problems process groups of equal-weight edges, test what each group would connect, roll the test back, and then commit. The base algorithm is in the Kruskal walkthrough.

Rollback versus the alternatives

The online structures (the Holm, de Lichtenberg and Thorup structure, link-cut trees for forests) handle deletions as they arrive but are much harder to implement and slower in practice. If your queries can be batched, even with some delay, the offline walk is usually the better engineering choice. Union-find variants compares rollback with the other variants of the structure.

Failure modes

• Path compression left on. The most common bug. A helper that compresses, or a library DSU used by mistake, silently corrupts state after the first rollback. Make find read-only and assert in tests that a find leaves the parent array unchanged.
• Missing no-op records. Checkpoints measured by log length go wrong if redundant unions push nothing in one code path and something in another. Pick one rule.
• Rolling back out of order. Restoring an outer checkpoint while an inner caller still expects its state is a logic error the structure cannot detect. Keep checkpoints in a strict stack, ideally tied to the call stack as in the walk above.
• Non-invertible aggregates. Undoing a minimum or a maximum by subtraction does not work. Store the old value.
• Duplicate edges. If the same edge can be added twice before it is deleted, pair each delete with the right add (a multiset of open intervals per edge), or lifetimes will be wrong.

Trade-offs

Rollback costs you the near-constant amortised find: you pay O(log n) per find instead. For a million elements that is at most 20 pointer hops, often far fewer, which is usually acceptable. In exchange you get exact, cheap undo with memory proportional to the number of live unions. The offline walk adds a log m factor and needs every operation in advance, which rules it out for interactive systems but fits batch analytics, replaying a log of network changes, and contest problems. Persistence is the right tool only when you must revisit arbitrary old versions rather than unwind in order.

What to do next

1. Implement the RollbackDSU above and write a test that unions random pairs, takes nested checkpoints, rolls back, and compares every array with a saved copy.
2. Add a brute-force checker and compare the offline walk with it on thousands of small random cases before trusting it on large inputs.
3. Extend the root state with one aggregate you need (component sum, a flag) and decide whether its undo record stores an operation or an old value.
4. Solve a leave-one-out problem: for each edge, report the number of components without it, using two lifetimes per edge.
5. Review Mo's algorithm, another way to reorder offline queries, and decide which fits your next batch workload.
6. Profile find depth on your real data. If the worst case dominates, check that union by size is actually applied on every path.