Wait, What?
Sometimes the easiest way to handle deletion is to travel back to a state before the insertion happened.
Ordinary disjoint-set union is excellent when edges are only added. Deletions are harder because path compression and destructive parent changes erase history. Rollback DSU changes the engineering contract: record enough mutations to undo unions, avoid transformations that are difficult to reverse, and process dynamic connectivity offline along a recursion over time.
Quick Answer
Learn rollback DSU through ordinary DSU → union-by-size → mutation log → snapshot → rollback → edge active intervals → segment tree over time → DFS apply/query/undo → complexity trade-off.
1. Master Ordinary DSU First
A DSU maintains connected components under union operations. Find identifies a component representative; union joins two components. Union-by-size or rank keeps trees shallow. Before rollback, learners should trace parent and size arrays by hand.
2. Why Path Compression Becomes Awkward
Path compression may rewrite many parent pointers during a single find. Those changes are excellent for ordinary DSU performance but create a large, implicit history that must be reversed. Rollback implementations therefore commonly keep union-by-size while omitting path compression, preserving logarithmic tree height and making mutations explicit.
3. Log Every Reversible Mutation
When two roots are joined, record the information needed to restore the previous state: which root became a child and the old size of the surviving root, or an equivalent mutation record. A no-op union between already-connected vertices must also have well-defined rollback behaviour.
4. Snapshots Are Just History Positions
Before entering a temporary computation, remember the current length of the change stack. Apply unions freely. When leaving, pop and reverse mutations until the stack returns to that saved length. This turns a mutable structure into a controlled reversible workspace.
5. Dynamic Connectivity Becomes an Offline Time Problem
If all add-edge, remove-edge and connectivity-query operations are known in advance, determine the time interval during which each edge is active. The problem is no longer “delete an edge from DSU now.” It becomes “apply this edge exactly to the time regions where it exists.”
6. Put Edge Lifetimes Into a Segment Tree Over Time
Build a segment tree whose leaves represent query times. Insert each edge into the O(log q) tree nodes whose intervals partition its active lifetime. During a depth-first traversal, every node contributes edges that are active throughout that whole time interval.
7. Apply, Answer, Undo
At a segment-tree node, save a DSU snapshot, union all edges stored there, recurse into children, answer connectivity queries at leaves, then rollback to the saved snapshot. The same edge can therefore influence exactly the appropriate time interval without ever requiring an online delete operation.
8. Trace a Five-Event Timeline
Use two edge additions, one connectivity query, one deletion and another query. First convert additions and deletions into active intervals. Then place those intervals into the time tree. Finally trace the DFS change stack. This three-representation exercise—events, intervals, recursion—is the key learning bridge.
9. The Trade-Off Is Deliberate
Rollback DSU gives up path compression and requires offline knowledge, but gains reversible state and elegant divide-and-conquer processing. It is not a replacement for fully dynamic online connectivity structures. It is a different solution to a different information contract.
Common Failure States
- Using path compression without logging every changed pointer.
- Forgetting to restore component sizes during rollback.
- Mishandling repeated additions or removals of the same edge.
- Using inclusive/exclusive time boundaries inconsistently.
- Rolling back too far after returning from one recursion branch.
- Claiming an offline method solves arbitrary online deletions.
Practice Ladder
- Trace ordinary union-by-size DSU.
- Add a change stack and undo one union.
- Create nested snapshots and roll back correctly.
- Convert an event stream into edge lifetimes.
- Place lifetimes into a segment tree over time.
- Trace DFS apply/query/undo on a small graph.
- Compare rollback DSU with fully dynamic online connectivity requirements.
Learning Hall Boundary
This article owns reversible union-find and its offline dynamic-connectivity application. The existing DSU and dynamic-graph articles remain the canonical owners of ordinary connectivity and the broader dynamic-graph landscape.
Evidence Boundary
Rollback DSU is a standard competitive-programming and offline-algorithm technique built from reversible union-by-size operations. Complexity depends on the surrounding time-decomposition method and event model. The technique should not be described as path-compressed DSU with free deletion; its strength comes from explicitly changing those assumptions.
Professional rule: understand rollback DSU when you can name every mutation that must be reversed, convert dynamic edge existence into time intervals and explain why offline recursion turns deletion into rollback.
