Disjoint-set rollback: restore an earlier connectivity checkpoint

Last updated: 5 Oct 20269 min read

tutorial

A rollback disjoint-set structure groups connected vertices while recording every successful union's parent and size changes. A checkpoint is the current history length. Rolling back pops changes until that length is restored. Union by size bounds tree height without path compression; compressing paths during find would change many parents that this short history does not record. A union of already connected vertices changes no state and adds no history entry. This program supports checkpointed unions in one mutable timeline. It does not remove an arbitrary historical edge while keeping later unrelated unions; that requires an offline interval scheme or a different connectivity structure.

Operational case

Depots D-19 and D-26 are joined permanently for this local scenario. A checkpoint is taken. A proposed bridge joins D-26 to D-47, making D-19 and D-47 connected. Rolling back to the checkpoint removes that temporary connectivity while preserving the D-19 to D-26 union. The printed result first reports true, then false and true. A caller should use checkpoints in a stack-like exploration: a saved integer alone cannot distinguish a stale token from a later branch that happens to have the same history length after rollback and new unions.

Working Python program

class RollbackConnectivity:
    def __init__(self, depot_ids):
        self.parent = {depot_id: depot_id for depot_id in depot_ids}
        self.size = {depot_id: 1 for depot_id in depot_ids}
        self.history = []

    def find(self, depot_id):
        current = depot_id
        while self.parent[current] != current:
            current = self.parent[current]
        return current

    def connected(self, first_depot, second_depot):
        return self.find(first_depot) == self.find(second_depot)

    def join(self, first_depot, second_depot):
        first_root = self.find(first_depot)
        second_root = self.find(second_depot)
        if first_root == second_root:
            return False
        if self.size[first_root] < self.size[second_root]:
            first_root, second_root = second_root, first_root
        self.history.append((second_root, first_root, self.size[first_root]))
        self.parent[second_root] = first_root
        self.size[first_root] += self.size[second_root]
        return True

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

    def rollback(self, checkpoint):
        if checkpoint < 0 or checkpoint > len(self.history):
            raise ValueError("checkpoint outside active history")
        while len(self.history) > checkpoint:
            child, root, old_size = self.history.pop()
            self.parent[child] = child
            self.size[root] = old_size


network = RollbackConnectivity(("D-19", "D-26", "D-47", "D-52"))
network.join("D-19", "D-26")
before_bridge = network.checkpoint()
network.join("D-26", "D-47")
print(network.connected("D-19", "D-47"))
network.rollback(before_bridge)
print(network.connected("D-19", "D-47"), network.connected("D-19", "D-26"))

Output

True
False True

Time, space, and tradeoff

Without path compression, union by size gives O(log n) worst-case find and union for n depots. A checkpoint is O(1). Rolling back u successful unions takes O(u) time, with O(1) restore work per recorded change. Parent and size maps use O(n) space, and the history uses O(u) space since the oldest retained checkpoint. The code assumes a fixed depot set and a single writer. A fully changing graph with edge lifetimes can pair rollback DSU with an offline time-interval decomposition, but that scheduling layer is not implemented here.

Common Mistakes

Do not enable unrecorded path compression and expect rollback to restore every parent.
Do not record a redundant union as a connectivity change.
Do not treat a history-length token as a durable cross-process version.
Do not claim this method supports arbitrary online edge removal.

Connected lessons

Apply this operation in the depot rollback project, then check the deletion and route quiz.

Offline connectivity: edge lifetimes and rollback unions extends this operational boundary.

Potential disjoint sets: preserve numeric differences across merges adds a distinct structure contract to compare.

Moveable disjoint sets: transfer one shipment without splitting its old tree adds a related structure with a different operation boundary.

data structures

range-query-structures