↩ back to Disjoint Set

Offline Dynamic Connectivity

Every earlier Disjoint Set entry answers "same set?" as the graph changes live, one union at a time. This page asks a different kind of question: given a whole batch of edges, each known in advance to be active only during some span of time, and a whole batch of "connected at time t?" queries — also all known in advance — answer every query correctly, as cheaply as possible, in one pass. Nothing here is interactive in the online sense; the entire timeline is known before the first query is answered, which is exactly what makes it possible to do far less work than replaying the graph from scratch at every queried instant.

The technique Union-Find with Rollback's own page names directly: recurse over time the way a segment tree recurses over array indices, except each tree node now covers a range of time instead of a range of indices. Decompose every edge's active window into the handful of tree nodes that exactly cover it, union those edges in on the way down, answer any query pinned to a leaf the moment that leaf is reached, and undo — in exact reverse order — on the way back up before a sibling range starts. That undo has to be exact and cheap for every one of the (possibly many) tree nodes visited, which is exactly the shape Union-Find with Rollback's strictly last-in-first-out O(1) undo was built for.

Try it

A fixed graph on 8 elements (0-7) and 6 edges, each active only during its own [start, end) window over 8 instants of time, t = 0 through 7. Eight queries are pinned one per instant. Press Step to walk the DFS one move at a time: entering a segment-tree node unions in whatever edges are assigned there (accent, solid border); finishing a node — after both its children are fully done — undoes exactly those unions before control returns to its parent. Watch the union-find panel below the tree update live, and watch two of the eight queries flip between true and false as the same pair of elements drifts apart and back together purely because of which edges happen to be active at that instant.

Why it works

Building the tree. The timeline [0, T) is split the same way a segment tree splits an index range: node 1 covers the whole thing, and every internal node's two children split its range exactly in half, down to T leaves, each one instant wide. For each edge's [start, end) window, the same range-decomposition walk a segment tree range-update uses finds every canonical node whose own range sits fully inside [start, end) and appends the edge to that node's list — never more nodes than necessary, and never a node whose range only partially overlaps.

The DFS. Visiting a node means: union every edge on that node's list into the shared Union-Find with Rollback structure first, before touching either child. That's what makes the recursion correct — every edge active anywhere inside a range is active for that range's entire depth-first subtree, so applying it once at the highest node that range is fully covered by is equivalent to applying it at every leaf underneath, without repeating the work leaf by leaf. Reaching a leaf means every edge active at that exact instant is already unioned in — the ones assigned to the leaf itself, plus every one assigned to an ancestor further up the current path — so any query pinned to that leaf gets a correct answer straight off the live structure, no separate rebuild required.

The undo. Once both of a node's children are fully done, that node's own edges need to stop being active before its parent's other child starts — otherwise an edge that was only ever supposed to be visible on one side of the tree leaks into the other. Undoing in exact reverse order, one union at a time, is precisely what Union-Find with Rollback's history stack does in O(1) per union — and because recursion's own call stack unwinds in the same strict last-in-first-out order the edges were pushed in, "undo everything this node pushed, right before returning" is always safe: nothing pushed after those unions is still live by the time they're popped.

Reference implementation

Matches the demo above exactly. RollbackDSU is the same structure as Union-Find with Rollback's own reference implementation, reused unmodified.

class RollbackDSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.history = [];
  }
  find(x) { while (this.parent[x] !== x) x = this.parent[x]; return x; }
  union(x, y) {
    let rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false; // already together — nothing pushed, nothing to undo
    if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];
    const rankBumped = this.rank[rx] === this.rank[ry];
    this.history.push({ child: ry, parentRoot: rx, rankBumped });
    this.parent[ry] = rx;
    if (rankBumped) this.rank[rx]++;
    return true;
  }
  undo() {
    const { child, parentRoot, rankBumped } = this.history.pop();
    this.parent[child] = child;
    if (rankBumped) this.rank[parentRoot]--;
  }
  connected(x, y) { return this.find(x) === this.find(y); }
}

// Segment tree over [0, T): node 1 is the root, node i's children are 2i and 2i+1.
function buildRanges(node, lo, hi, into) {
  into[node] = { lo, hi, edges: [] };
  if (hi - lo === 1) return;
  const mid = (lo + hi) >> 1;
  buildRanges(node * 2, lo, mid, into);
  buildRanges(node * 2 + 1, mid, hi, into);
}

// Decompose one edge's [start, end) window onto its canonical tree nodes.
function insertEdge(node, ranges, edge) {
  const { lo, hi } = ranges[node];
  if (edge.end <= lo || hi <= edge.start) return;               // no overlap — skip
  if (edge.start <= lo && hi <= edge.end) { ranges[node].edges.push(edge); return; } // fully covered
  insertEdge(node * 2, ranges, edge);
  insertEdge(node * 2 + 1, ranges, edge);
}

// One DFS answers every query. queryByTime maps a leaf's instant to its pinned query, if any.
function solve(node, ranges, dsu, queryByTime, answers) {
  const { lo, hi, edges } = ranges[node];
  let pushed = 0;
  for (const e of edges) if (dsu.union(e.u, e.v)) pushed++;

  if (hi - lo === 1) {
    const q = queryByTime[lo];
    if (q) answers[q.index] = dsu.connected(q.u, q.v);
  } else {
    solve(node * 2, ranges, dsu, queryByTime, answers);
    solve(node * 2 + 1, ranges, dsu, queryByTime, answers);
  }

  for (let i = 0; i < pushed; i++) dsu.undo(); // exact reverse order, before returning to the parent
}

Pitfalls

Skipping the undo doesn't just leave stray unions lying around — it silently corrupts later, unrelated queries. Checked directly against the demo's own 6 edges and 8 queries: with the undo loop removed entirely (every union still happens, nothing is ever reversed), every one of the 8 queries reports true — including the 3 (at t=4, t=5, and t=7) whose correct answer is false. Nothing about those 3 queries themselves is unusual; each just happens to be reached only after a union from an edge whose active window had already ended got pushed by an earlier sibling range and never popped. The bug isn't localized to the pair being queried — one missing undo anywhere earlier in the traversal can flip any later query pinned underneath a different, unrelated part of the tree.

The window is half-open — end itself is excluded — and getting that boundary backwards is a real, checkable answer flip, not a rounding nuance. Edge (2,3)'s window is [0, 4): active at t = 3, not active at t = 4. Query (0,3) is pinned at both t = 2 (while edge (1,2)'s own [2,6) window has already started, chaining 0-1-2-3 into one set — answer true) and again at t = 4 (edge (2,3) has just dropped out, splitting that set — answer false). Swap the insert/query comparisons from edge.end <= lo to edge.end < lo (treating end as included) and this exact instance double-counts: element 3 stays reachable from 0 one instant longer than the data actually says it should.

Complexity

Time: each edge's [start, end) window is decomposed onto at most 2·log₂T canonical tree nodes, the same bound a segment tree range-update obeys — measured directly on the demo's own 6 edges over T = 8 (so log₂T = 3, a 6-node worst case per edge): the real counts are 1, 1, 2, 3, 2, and 2 tree-node assignments per edge, 11 total, well under the 36-assignment worst case, because most of these windows already sit close to power-of-two boundaries. Every one of those assignments does one union, and the DFS undoes exactly as many as it applies, so total union/undo calls are both O(m log T). Each call costs up to O(log n) — Union-Find with Rollback's own Complexity section measures that bound directly (a 64-element worst-case tree costs 6 hops per find, forever, since nothing here ever compresses a path). Altogether: O((n + m·log T)·log n), commonly written O((n + m)·log n·log m) once T is bounded by the number of operations. Space: O(n) for the Union-Find arrays, O(m log T) for the tree's edge lists, and O(log T) for the recursion depth itself — the history stack never holds more than the edges on the single current root-to-node path, since everything a node pushes is undone before its parent's next child starts.

This site's guide, Choosing a Union-Find Variant, is where this technique is first named as the reason Union-Find with Rollback's narrow, strictly last-in-first-out undo is worth having at all. For the fully online version of this same question over a forest specifically — no whole-timeline-up-front requirement, edges linked and cut in any order — see Link-Cut Tree.