Offline Dynamic Connectivity, in depth: edge lifetimes, a segment tree over time with rollback union-find, and the deletion-time spanning forest

The problem, stated precisely

Fix n vertices numbered 0 to n-1 and a list of q operations: add u v, remove u v, connected u v and components. Operation t sees the graph produced by operations 0 through t-1. The answers must equal what a naive simulator would give: rebuild a union-find from the live edges at every query. That simulator costs O(q times m) and is the reference you test against.

The offline trick is to stop thinking about operations and start thinking about lifetimes. An edge that is added at time a and removed at time b is present for every query in the half-open interval [a, b). An edge that is never removed lives in [a, q). Once every edge is an interval, the question at time t becomes: union every edge whose interval contains t, then look. The two methods below differ in how they avoid redoing that work for every t.

From operations to edge lifetimes

Turning operations into intervals is where most bugs live, so treat it as its own step with explicit rules.

• Normalise the pair. Store an undirected edge as (min(u, v), max(u, v)) so that add 3 1 and remove 1 3 refer to the same edge.
• Count copies. If the same edge can be added twice, connectivity only cares whether at least one copy is live. Keep a count; open the interval when it goes from 0 to 1 and close it when it returns to 0. Pairing each removal with the most recent add instead produces overlapping intervals that are harmless but wasteful.
• Close the leftovers. After the scan, every still-open edge gets the interval [start, q).
• Self-loops. They never change connectivity; drop them.
• Removing an absent edge. Decide the contract. The code below ignores it, matching a simulator that ignores it; in production log data it is usually a sign of a lost event and deserves an alert.

Method 1: a segment tree over time

Build a segment tree over the time axis [0, q). Insert each edge interval into the O(log q) canonical nodes that exactly cover it, the same decomposition a range update uses. Then walk the tree depth first with a union-find that supports rollback: on entering a node, union all of its edges; at a leaf t, the structure contains exactly the edges alive at t, so answer operation t; on leaving, undo the unions made at that node. Rollback is cheap if the union-find uses union by size and no path compression, because each union changes one parent pointer and one size, which a stack can restore. The rollback structure itself, with parity for bipartiteness, is covered in union-find with rollback; here the focus is the full connectivity pipeline and its edge cases.

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n
        self.history = []          # (absorbed root, kept root) per successful union

    def find(self, x):             # no path compression: rollback must stay O(1)
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] > self.size[b]:
            a, b = b, a            # attach the smaller tree a under b
        self.parent[a] = b
        self.size[b] += self.size[a]
        self.components -= 1
        self.history.append((a, b))
        return True

    def rollback(self, mark):
        while len(self.history) > mark:
            a, b = self.history.pop()
            self.parent[a] = a
            self.size[b] -= self.size[a]
            self.components += 1


def offline_connectivity(n, ops):
    """ops: ("add", u, v), ("remove", u, v), ("connected", u, v), ("components",)."""
    q = len(ops)
    copies, opened, intervals = {}, {}, []
    for t, op in enumerate(ops):
        if op[0] in ("add", "remove"):
            u, v = sorted(op[1:])
            if u == v:
                continue                         # self-loop: never changes connectivity
            k = copies.get((u, v), 0)
            if op[0] == "add":
                if k == 0:
                    opened[(u, v)] = t           # first live copy opens the interval
                copies[(u, v)] = k + 1
            elif k > 0:
                copies[(u, v)] = k - 1
                if k == 1:
                    intervals.append((opened.pop((u, v)), t, (u, v)))
    for edge, start in opened.items():
        intervals.append((start, q, edge))       # never removed: alive to the end

    seg = [[] for _ in range(4 * max(q, 1))]

    def insert(node, lo, hi, l, r, edge):        # node covers times [lo, hi)
        if r <= lo or hi <= l:
            return
        if l <= lo and hi <= r:
            seg[node].append(edge)
            return
        mid = (lo + hi) // 2
        insert(2 * node, lo, mid, l, r, edge)
        insert(2 * node + 1, mid, hi, l, r, edge)

    for l, r, edge in intervals:
        if l < r:
            insert(1, 0, q, l, r, edge)

    dsu, answers = RollbackDSU(n), {}

    def solve(node, lo, hi):
        mark = len(dsu.history)
        for u, v in seg[node]:
            dsu.union(u, v)
        if hi - lo == 1:
            op = ops[lo]
            if op[0] == "connected":
                answers[lo] = dsu.find(op[1]) == dsu.find(op[2])
            elif op[0] == "components":
                answers[lo] = dsu.components
        else:
            mid = (lo + hi) // 2
            solve(2 * node, lo, mid)
            solve(2 * node + 1, mid, hi)
        dsu.rollback(mark)

    if q:
        solve(1, 0, q)
    return [answers[t] for t in sorted(answers)]

This code was checked against the naive simulator on 3,000 random timelines with up to seven vertices, duplicate adds, removals of absent edges and self-loops. Recursion depth is about log2 q, so Python's default limit is not a problem; the cost is constant factors, and for q in the millions you would port it to C++ or Rust with flat arrays.

Complexity. Each interval lands in at most about 2 log q nodes, so there are O(q log q) unions in total, and each union and rollback costs O(log n) because union by size bounds tree height. The total is O(q log q log n) time and O(n + q log q) memory. Every answer is correct because a leaf's ancestors are exactly the canonical nodes of the intervals that contain that time, so the structure at the leaf holds exactly the live edges.

Worked example

Take five vertices and ten operations, indexed by time:

The lifetimes are 0-1 on [0, 8), 1-2 on [1, 4), 2-3 on [3, 10) and 0-3 on [6, 10). The diagram shows where each lands. Edge 0-1 covers all of [0, 5) so it sits high in the tree, then [5, 7) and [7, 8). Edge 1-2 needs three small nodes because its interval is short and misaligned.

Follow the walk to leaf 5. The path is [0,10), [5,10), [5,7), [5,6), collecting 2-3 and 0-1. Vertices 0 and 3 are in different components, so the answer is false. Leaf 9 collects 2-3 and then 0-3 at [7,10); 0, 3 and 2 are joined, so it answers true even though 0-1 has gone. Leaf 7 has 2-3, 0-3 and 0-1, giving components {0, 1, 2, 3} and {4}: two.

Method 2: a spanning forest keyed by deletion time

The second method avoids the log q factor by keeping one well-chosen spanning forest instead of rebuilding. Since the input is offline, every edge's deletion time is known when it is inserted; use it as a weight. Maintain a maximum spanning forest with respect to deletion time, using a link-cut tree that can answer path-minimum queries.

for t, op in enumerate(ops):
    if op is add(u, v) with deletion time d:
        if u == v: continue
        if not lct.connected(u, v):
            lct.link(u, v, weight=d); tree.add(edge)
        else:
            e_min = lct.path_min(u, v)            # tree edge on the u-v path with smallest d
            if e_min.d < d:
                lct.cut(e_min); tree.remove(e_min)
                lct.link(u, v, weight=d); tree.add(edge)
            # otherwise the new edge is redundant and is simply never used
    elif op is remove(edge):
        if edge in tree: lct.cut(edge); tree.remove(edge)
    elif op is connected(u, v):
        answer lct.connected(u, v)

Why is no replacement edge ever needed after a cut? Two facts. Removing an edge never breaks maximality, because the edge being deleted now has the smallest deletion time of all live edges, and removing the minimum element from a maximum spanning forest leaves a maximum spanning forest of what remains. And in a maximum spanning forest, any live non-tree edge f whose cycle contains tree edge e satisfies d(f) <= d(e), otherwise swapping them would give a heavier forest. When e is deleted at time d(e), such an f would have to be deleted no later, but f is still alive and deletion times are distinct, a contradiction. So the forest always spans exactly the components of the live graph.

Each operation is a constant number of link-cut operations, so the total is O((n + q) log n) amortised. Components can be counted by tracking links and cuts. Implementing link-cut trees with edge weights means representing each edge as an extra node; see link-cut trees for the splay mechanics.

Extensions and limits

• Component sizes and aggregates. The rollback union-find can carry any value that merges with an invertible or stackable update, such as sizes, sums or a bipartiteness parity, as long as the rollback record restores it.
• Queries about edge weights. Offline minimum spanning tree with changing edge weights uses the same time-segment idea with a more involved contraction step; budget for it separately.
• Batches of snapshots. If you only need answers at a few checkpoints, sort edges by lifetime and run the divide and conquer over checkpoints instead of every operation; see divide and conquer for the pattern.
• When offline fails. If a query depends on an earlier answer, as in problems that encode the next operation using the last answer, you do not know the future and need an online structure.

Failure modes

• Path compression in the rollback DSU. It rewrites many pointers per find, so rollback becomes wrong unless every write is logged. Use union by size alone.
• Unnormalised edges. Treating (3, 1) and (1, 3) as different edges leaves intervals open forever and answers come back connected when they should not.
• Off-by-one lifetimes. A query at the same time as a removal must not see the edge; half-open intervals [a, b) with the removal at b get this right.
• Segment tree size. Allocate 4q nodes or use an iterative layout; an empty operation list needs a guard, as in the code.
• Memory at scale. Storing O(q log q) edge copies in Python lists is the real limit around a few million operations; use flat arrays and integer edge ids.
• Ties in the link-cut method. Give never-deleted edges deletion time q and break ties consistently, or the replacement argument above does not hold.

Trade-offs

What to do next

1. Write the naive simulator first and keep it as the oracle for randomised tests.
2. Implement interval building with normalisation, copy counts and end-of-input closing; test it alone.
3. Add the rollback union-find without path compression and the segment tree over time, then compare against the oracle on thousands of random small timelines.
4. Extend the stored state only when needed: component counts, sizes, parity.
5. Profile on realistic sizes; port to flat arrays before reaching for the link-cut method.
6. Use the link-cut method only when the log q factor is the measured bottleneck, and test it against the segment tree version.