Rollback Disjoint Set
Create nested connectivity checkpoints, undo unions and branch into a different future partition.
By Riano · Published · Updated · Report a correction
Rollback Disjoint Set
A Rollback Disjoint Set (also known as a persistent DSU or DSU with rollback) is a data structure that extends the standard Disjoint Set Union (DSU) by allowing us to undo previous union operations and return to an earlier structural state.
Worked Example
Let's trace a rollback DSU with 5 elements (0 to 4). Initially, each element is in its own set. We use union-by-size and no path compression. If sizes are equal, the smaller root becomes the new parent.
- Initial State: Sets are [0], [1], [2], [3], [4]. Component count is 5.
- U 0 1: Size of 0 is 1, size of 1 is 1. Equal sizes, so 0 (smaller root) becomes parent of 1. Sets: [0, 1], [2], [3], [4]. Component count is 4.
- S: We push the current state to the snapshot stack. Open snapshots is 1.
- U 1 2: Root of 1 is 0. Root of 2 is 2. Size of 0 is 2, size of 2 is 1. Root 2 is attached to 0. Sets: [0, 1, 2], [3], [4]. Component count is 3.
- R: We pop the latest snapshot. The state reverts to before ‘U 1 2’. Sets: [0, 1], [2], [3], [4]. Component count is 4. Open snapshots is 0.
- U 3 4: Size of 3 is 1, size of 4 is 1. 3 becomes parent of 4. Sets: [0, 1], [2], [3, 4]. Component count is 3.
Experiment
You can interact with the Rollback Disjoint Set in the module: Rollback Disjoint Set.
- Enter the operations string
U 0 1; S; U 1 2; R; U 3 4in the “Operations” control. - Click the Step button to trace how the parent pointers update and how snapshots are taken.
- Click the Finish button to see the final components and component count.
- Verify that after the rollback
R, the components revert and branch into a different future partition whenU 3 4is executed.
Limitations
The implementation shown relies purely on union-by-size without path compression. Path compression is omitted because it amortizes the time complexity but updates the parent pointers of many nodes. Saving those changes requires more complex history tracking (e.g., an undo stack of individual edge modifications) or full state duplication. This module uses full array duplication for snapshots, which is simple but takes O(N) time and space per snapshot. A production DSU with rollback typically tracks individual assignments on a stack to achieve O(log N) per operation.
References
For more algorithmic details on Disjoint Set Union with rollback and its application in offline dynamic connectivity, see:
- Deleting from a data structure in O(T(n) log n) (CP-Algorithms) - Explains the rollback trick and how it supports offline deletions.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Rollback Disjoint Set module.
Try Rollback Disjoint Set on Riano →