Offline connectivity: edge lifetimes and rollback unions

A rollback disjoint-set can undo recent unions but cannot remove one arbitrary active edge while preserving later changes. If all add, remove, and connectivity questions are known in advance, convert each edge's active span into a half-open interval on the event timeline. A segment tree over time stores that edge in nodes whose ranges fit inside its span. A depth-first walk unions each node's edges, answers questions at leaves, then rolls back to the checkpoint held before entering the node. The resulting connectivity at a query time contains exactly the edges active at that time. This program rejects duplicate adds, removing an absent edge, unknown depots, self-edges, and unknown actions. It is an offline batch algorithm, not a live graph service.

Operational case

The event stream adds D-19 to D-26, asks whether D-19 reaches D-47, adds D-26 to D-47, asks again, removes that second edge, and asks a third time. The answers are false, true, false. The first edge spans the whole timeline after its addition; the second spans only the interval before removal. Each active interval is attached to O(log Q) time-tree nodes for Q events. The traversal can restore the disjoint-set state after evaluating an earlier time branch without rebuilding the graph from zero for each question. Event order matters: an edge added at position i is active for later questions until its removal event.

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


def answer_timeline(depot_ids, events):
    depot_ids = tuple(depot_ids)
    known = set(depot_ids)
    if len(known) != len(depot_ids):
        raise ValueError("duplicate depot ID")
    if not events:
        return []
    active_since = {}
    intervals = []
    for time, (action, first, second) in enumerate(events):
        if first not in known or second not in known or first == second:
            raise ValueError("unknown or repeated depot")
        if action not in {"add", "remove", "ask"}:
            raise ValueError("unknown action")
        edge = tuple(sorted((first, second)))
        if action == "add":
            if edge in active_since:
                raise ValueError("edge already active")
            active_since[edge] = time
        elif action == "remove":
            if edge not in active_since:
                raise ValueError("edge not active")
            intervals.append((active_since.pop(edge), time, edge))
    for edge, start in active_since.items():
        intervals.append((start, len(events), edge))

    buckets = [[] for _ in range(4 * len(events))]

    def assign(node, left, right, start, stop, edge):
        if start <= left and right <= stop:
            buckets[node].append(edge)
            return
        middle = (left + right) // 2
        if start < middle:
            assign(2 * node, left, middle, start, stop, edge)
        if stop > middle:
            assign(2 * node + 1, middle, right, start, stop, edge)

    for start, stop, edge in intervals:
        assign(1, 0, len(events), start, stop, edge)

    network = RollbackConnectivity(depot_ids)
    answers = []

    def visit(node, left, right):
        checkpoint = network.checkpoint()
        for first, second in buckets[node]:
            network.join(first, second)
        if right - left == 1:
            action, first, second = events[left]
            if action == "ask":
                answers.append(network.connected(first, second))
        else:
            middle = (left + right) // 2
            visit(2 * node, left, middle)
            visit(2 * node + 1, middle, right)
        network.rollback(checkpoint)

    visit(1, 0, len(events))
    return answers


changes = [
    ("add", "D-19", "D-26"),
    ("ask", "D-19", "D-47"),
    ("add", "D-26", "D-47"),
    ("ask", "D-19", "D-47"),
    ("remove", "D-26", "D-47"),
    ("ask", "D-19", "D-47"),
]
print(answer_timeline(("D-19", "D-26", "D-47"), changes))

Output

[False, True, False]

Time, space, and tradeoff

For V depots, Q events, and I edge-active intervals, placing intervals costs O(I log Q) time and stored references. With union by size and no path compression, find and union cost O(log V), so a conservative total is O(Q + (I log Q + A) log V), where A is the number of questions. The segment tree, events, answers, and stored intervals use O(Q + I log Q) space; disjoint-set arrays and active rollback history add O(V + I) on a single traversal path. The model assumes a fixed depot set and one active copy of each undirected edge. Parallel edges, online arrival, and persistence need separate contracts.

Common Mistakes

Do not remove one DSU edge directly and assume other unions remain valid.
Do not leave an edge active beyond its removal position in the time tree.
Do not use path compression without recording every parent change for rollback.
Do not call an offline batch answer a live update API.

Connected lessons

Apply this contract in the reversible depot release project, then check the operations quiz.

Online connectivity: answer after each edge change examines the next boundary.