Dynamic Connectivity

The Core Intuition: Connectivity Has a Time Dimension

Static connectivity asks whether a path exists in one fixed graph. Dynamic connectivity asks the same question after every change. The graph is no longer one object; it is a sequence $G_0,G_1,\ldots,G_{q-1}$ produced by edge insertions and deletions.

The query remains simple:

The challenge is deletion. Insertions only merge components, so Union-Find works beautifully. Deletions can split a component—or change nothing because another route survives. Determining which case occurred is the real dynamic-connectivity problem.

Choose the Update Model Before the Data Structure

Why Ordinary Union-Find Cannot Delete

A DSU stores a partition of vertices, not the proof that produced that partition. After unions $(A,B)$ and $(B,C)$, it knows only that $A,B,C$ share a representative. If edge $BC$ disappears, the DSU cannot tell whether another path still connects B and C.

flowchart TD
D[Delete active edge] --> T{Forest edge?}
T -->|No| U[Components unchanged]
T -->|Yes| S[Cut forest into two trees]
S --> R{Replacement edge crosses cut?}
R -->|Yes| J[Promote and relink]
R -->|No| C[Component truly splits]

The Offline Escape Hatch

When the whole operation log is available, stop thinking of an edge as something that must be physically deleted from a DSU. Instead, compute the interval of times during which that edge exists. Then arrange computation so the edge is added only while visiting those times.

1. Pair each insertion with its deletion. This produces a half-open lifetime $[l,r)$.
2. Store the edge on a segment tree over time. Each interval is covered by $O(\log q)$ tree nodes.
3. Depth-first traverse the time tree. Entering a node activates its stored edges.
4. Answer queries at leaves. The DSU then contains exactly the edges active at that time.
5. Rollback when leaving. Restore the DSU snapshot so sibling time ranges do not inherit one another's edges.

Step 1: Convert Events into Edge Lifetimes

Use the half-open convention $[l,r)$: an edge added at time $l$ is active starting at $l$, and an edge removed at time $r$ is already absent at $r$. An edge never removed receives $r=q$, one position past the final operation.

Our running sequence has eight operations:

Pairing rules

For a simple graph, normalize every undirected edge as $(\min(u,v),\max(u,v))$. Store its insertion time in a map. A removal closes the interval and clears the map entry. Remaining entries after the scan become $[l,q)$ intervals.

Step 2: Store Lifetimes in a Segment Tree over Time

A segment-tree node represents a time range. Store edge $e$ at a node when the node's whole range lies inside $e$'s lifetime. Recurse only into partial overlaps. Any interval $[l,r)$ decomposes into $O(\log q)$ disjoint canonical nodes.

For the running example:

• AB on $[0,8)$ is stored once at the root.
• BC on $[1,5)$ is stored at $[1,2)$, $[2,4)$, and $[4,5)$.
• CD on $[3,8)$ is stored at $[3,4)$ and $[4,8)$.

Step 3: Make Union-Find Reversible

A rollback DSU records every successful merge on a history stack. Before entering a segment-tree node, save the stack length. After finishing that node, pop changes until the saved length is restored.

The rollback invariant

At any segment-tree node representing range $[l,r)$, the DSU contains exactly the edges stored on the path from the root to that node. At a leaf $t$, those path edges are exactly the graph edges active at time $t$.

flowchart TD
S[Save history length] --> U[Union edges stored here]
U --> Q{Leaf?}
Q -->|Yes| A[Answer query]
Q -->|No| D[Visit both children]
A --> R[Rollback to snapshot]
D --> R

Implementation: Offline Dynamic Connectivity

The Python tab is an end-to-end solver for the running example. The C++ and Java tabs isolate the rollback DSU—the component most often implemented incorrectly—so it can be combined with the same interval and segment-tree traversal.

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.history = []

    def find(self, x):                 # deliberately no path compression
        while x != self.parent[x]:
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.history.append((b, a, self.size[a]))
        self.parent[b] = a
        self.size[a] += self.size[b]

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

    def rollback(self, snapshot):
        while len(self.history) > snapshot:
            child, root, old_size = self.history.pop()
            self.parent[child] = child
            self.size[root] = old_size

    def connected(self, a, b):
        return self.find(a) == self.find(b)


operations = [
    ("add", "A", "B"),
    ("add", "B", "C"),
    ("ask", "A", "C"),
    ("add", "C", "D"),
    ("ask", "A", "D"),
    ("remove", "B", "C"),
    ("ask", "A", "D"),
    ("ask", "A", "C"),
]

vertices = sorted({v for op in operations for v in op[1:]})
index = {v: i for i, v in enumerate(vertices)}
q = len(operations)
tree = [[] for _ in range(4 * q)]

def edge_of(op):
    u, v = index[op[1]], index[op[2]]
    return (u, v) if u < v else (v, u)

def add_interval(node, left, right, ql, qr, edge):
    if qr <= left or right <= ql:
        return
    if ql <= left and right <= qr:
        tree[node].append(edge)
        return
    middle = (left + right) // 2
    add_interval(node * 2, left, middle, ql, qr, edge)
    add_interval(node * 2 + 1, middle, right, ql, qr, edge)

started = {}
for time, op in enumerate(operations):
    if op[0] == "add":
        started[edge_of(op)] = time
    elif op[0] == "remove":
        edge = edge_of(op)
        add_interval(1, 0, q, started.pop(edge), time, edge)
for edge, start in started.items():
    add_interval(1, 0, q, start, q, edge)

dsu = RollbackDSU(len(vertices))
answers = []

def solve(node, left, right):
    saved = dsu.snapshot()
    for u, v in tree[node]:
        dsu.union(u, v)
    if right - left == 1:
        op = operations[left]
        if op[0] == "ask":
            answers.append((left, op[1], op[2],
                            dsu.connected(index[op[1]], index[op[2]])))
    else:
        middle = (left + right) // 2
        solve(node * 2, left, middle)
        solve(node * 2 + 1, middle, right)
    dsu.rollback(saved)

solve(1, 0, q)
for time, u, v, answer in answers:
    print(f"t={time}: {u}-{v} {answer}")

#include <iostream>
#include <numeric>
#include <tuple>
#include <vector>
using namespace std;

class RollbackDSU {
    vector<int> parent, size;
    vector<tuple<int,int,int>> history; // child, root, old root size
public:
    explicit RollbackDSU(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) const {
        while (x != parent[x]) x = parent[x]; // no compression
        return x;
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        history.emplace_back(b, a, size[a]);
        parent[b] = a; size[a] += size[b];
    }
    int snapshot() const { return static_cast<int>(history.size()); }
    void rollback(int saved) {
        while (static_cast<int>(history.size()) > saved) {
            auto [child, root, oldSize] = history.back(); history.pop_back();
            parent[child] = child; size[root] = oldSize;
        }
    }
    bool connected(int a, int b) const { return find(a) == find(b); }
};

int main() {
    RollbackDSU dsu(4);
    int saved = dsu.snapshot();
    dsu.unite(0, 1); dsu.unite(1, 2);
    cout << boolalpha << dsu.connected(0, 2) << '\n'; // true
    dsu.rollback(saved);
    cout << dsu.connected(0, 2) << '\n';                 // false
}

import java.util.*;

public class RollbackConnectivity {
    record Change(int child, int root, int oldSize) {}

    static class RollbackDSU {
        int[] parent, size;
        ArrayList<Change> history = new ArrayList<>();

        RollbackDSU(int n) {
            parent = new int[n]; size = new int[n];
            for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        }
        int find(int x) {
            while (x != parent[x]) x = parent[x]; // no compression
            return x;
        }
        void unite(int a, int b) {
            a = find(a); b = find(b);
            if (a == b) return;
            if (size[a] < size[b]) { int temp = a; a = b; b = temp; }
            history.add(new Change(b, a, size[a]));
            parent[b] = a; size[a] += size[b];
        }
        int snapshot() { return history.size(); }
        void rollback(int saved) {
            while (history.size() > saved) {
                Change c = history.remove(history.size() - 1);
                parent[c.child()] = c.child();
                size[c.root()] = c.oldSize();
            }
        }
        boolean connected(int a, int b) { return find(a) == find(b); }
    }

    public static void main(String[] args) {
        RollbackDSU dsu = new RollbackDSU(4);
        int saved = dsu.snapshot();
        dsu.unite(0, 1); dsu.unite(1, 2);
        System.out.println(dsu.connected(0, 2)); // true
        dsu.rollback(saved);
        System.out.println(dsu.connected(0, 2)); // false
    }
}

Expected output for the full solver

t=2: A-C True
t=4: A-D True
t=6: A-D False
t=7: A-C False

When Queries Must Be Answered Online

An online fully dynamic structure cannot rearrange time. It commonly maintains a spanning forest plus non-tree edges. Insertions either link two trees or become redundant non-tree edges. Deleting a tree edge cuts the forest and triggers a search for a replacement edge crossing the new cut.

The classical Holm–de Lichtenberg–Thorup framework achieves polylogarithmic amortized update time by promoting edges through levels and bounding replacement searches. It is a major theoretical and engineering step beyond rollback DSU. Use it only when the online requirement is real.

Complexity and the Cost of Knowing the Future

The offline bound follows directly: at most $O(q)$ edge lifetimes are stored in $O(\log q)$ segment nodes each, and union by size without path compression gives $O(\log n)$ finds. Query leaves add only another $O(q\log n)$ term.

Networks That Refuse to Sit Still

Connectivity is only a yes/no component property. If queries ask shortest paths, flows, distances, or directed reachability, a connectivity structure is insufficient even if its update model matches.

Common Failure Modes

A practical decision checklist

From Union-Find to Fully Dynamic Forests

Union-Find solved the monotone version of connectivity: components merge but never split. Dynamic-tree representations later made link and cut operations efficient on forests. General fully dynamic connectivity added the harder replacement-edge problem for graphs with cycles.

The Holm–de Lichtenberg–Thorup work established a celebrated deterministic polylogarithmic framework for online updates. For offline workloads, segment trees over time and rollback DSU offer a much simpler lesson with the same underlying theme: preserve what stays valid, record exactly what changes, and undo only in a controlled order.