Explore modules

Rollback Disjoint Set

Create nested connectivity checkpoints, undo unions and branch into a different future partition.

Free theory article

Create nested connectivity checkpoints, undo unions and branch into a different future partition.

Concept & interpretation

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.

Experiment

You can interact with the Rollback Disjoint Set in the module: Rollback Disjoint Set.

  1. Enter the operations string U 0 1; S; U 1 2; R; U 3 4 in the “Operations” control.
  2. Click the Step button to trace how the parent pointers update and how snapshots are taken.
  3. Click the Finish button to see the final components and component count.
  4. Verify that after the rollback R, the components revert and branch into a different future partition when U 3 4 is executed.
Read the full free theory article