xii. Dynamic Connectivity

Connectivity under edge insertions and deletions.

Operations	Technique	Cost
insertions only	DSU	$O(\alpha )$
deletions only	reverse time, then DSU	$O(\alpha )$
both, offline	segment tree over time + rollback DSU	$O((n+q)\log q\log n)$
both, online, graph stays a forest	link-cut tree (LCT)	$O(\log n)$
both, online, general	Holm–de Lichtenberg–Thorup (HDT)	$O({\log }^{2}n)$ amortised
offline, with a maximum spanning forest by deletion time	link-cut tree keyed by deletion time	$O(q\log n)$
both, online, with MST maintenance	HDT extended with edge weights	$O({\log }^{4}n)$ amortised

Offline: segment tree over time

Each edge is alive on a set of time intervals. Insert each interval into the $O(\log q)$ segment-tree nodes covering it; DFS the tree, uniting a node’s edges on the way down and rolling them back on the way up. At leaf $t$ the DSU contains exactly the edges alive at time $t$. The DSU uses union by size and no path compression, so each union is undone in $O(1)$.

struct RollbackDSU {
    vector<int> p, s; vector<pair<int, int>> hist; int comps;
    RollbackDSU(int n) : p(n), s(n, 1), comps(n) { iota(all(p), 0); }
    int find(int v) const { while (p[v] != v) v = p[v]; return v; }
    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) { hist.push_back({-1, -1}); return false; }
        if (s[a] < s[b]) swap(a, b);
        hist.push_back({b, a}); p[b] = a; s[a] += s[b]; comps--; return true;
    }
    void undo() { auto [b, a] = hist.back(); hist.pop_back(); if (b >= 0) p[b] = b, s[a] -= s[b], comps++; }
};
struct OfflineConnectivity {                              // times 0..T-1
    int T; vector<vector<pair<int, int>>> seg;
    OfflineConnectivity(int T) : T(T), seg(4 * max(T, 1)) {}
    void addEdge(int l, int r, pair<int, int> e) { add(1, 0, T, l, r, e); }   // edge alive during [l, r)
    void add(int x, int lo, int hi, int l, int r, pair<int, int> e) {
        if (r <= lo || hi <= l) return;
        if (l <= lo && hi <= r) { seg[x].push_back(e); return; }
        int m = (lo + hi) / 2; add(2 * x, lo, m, l, r, e); add(2 * x + 1, m, hi, l, r, e);
    }
    template<class F> void run(RollbackDSU& d, F atLeaf, int x = 1, int lo = 0, int hi = -1) {
        if (hi < 0) hi = T;
        for (auto [u, v] : seg[x]) d.unite(u, v);
        if (hi - lo == 1) atLeaf(lo);
        else { int m = (lo + hi) / 2; run(d, atLeaf, 2 * x, lo, m); run(d, atLeaf, 2 * x + 1, m, hi); }
        for (int i = 0; i < sz(seg[x]); i++) d.undo();
    }
};
// lifetimes: map<pair<int,int>, int> start; on add: start[e] = t; on remove: addEdge(start[e], t, e), erase; at the end close the rest at T

Anything a DSU maintains reversibly can be answered at the leaves: component count, sizes, sums per component, bipartiteness (parity DSU), “number of edges inside each component”, and even a linear basis or a knapsack per component if it supports undo.

Proof: correctness and complexity

A segment-tree node’s edge list is applied exactly while the DFS is inside that node’s time range, and the canonical decomposition of $[l,r)$ means the edge is applied at leaf $t$ iff $t\in [l,r)$. Rollback restores the DSU to its exact previous state because every union changes one parent pointer and one size, which are recorded. Each edge interval is stored in $O(\log q)$ nodes, each union costs $O(\log n)$ (union by size keeps trees of height $\le {\log }_{2}n$, and without path compression find walks that height), so the total is $O((n+q)\log q\log n)$ plus $O(q)$ leaf work.

Offline via maximum spanning forest by deletion time

Process time forward and maintain a spanning forest that is maximal with respect to deletion time: when inserting edge $e$ that closes a cycle, find the cycle edge with the earliest deletion time (path minimum in a link-cut tree), and if it is earlier than $e$‘s, replace it with $e$. Then a tree edge’s deletion never has a replacement among non-tree edges (they all die earlier), so connectivity queries are answered by the forest. $O(q\log n)$ with an LCT.

Proof: no replacement is ever needed

Invariant: the forest is a maximum spanning forest of the current graph with weights = deletion times. A non-tree edge $f$ is never heavier than the lightest edge on its tree cycle (otherwise exchanging them would give a heavier forest). When the earliest-dying tree edge $e$ on some path is deleted, any non-tree edge $f$ that could reconnect its two sides lies on a cycle through $e$, so $f$ dies no later than $e$, i.e. $f$ is already gone. Hence deleting a tree edge truly disconnects the two sides, and the forest stays a maximum spanning forest.

Online: Holm–de Lichtenberg–Thorup

Each edge has a level $\ell \in [0,\log n]$; $F_i$ = spanning forest of edges with level $\ge i$, with the invariants $F_0\supseteq F_1\supseteq \dots$ and “every component of $F_i$ has at most $n/2^i$ vertices”. Forests are kept as Euler tour trees (ETT) that can report a non-tree edge incident to a component.

• Insert: level 0; tree edge if it connects two components of $F_0$, else non-tree.
• Delete a tree edge of level $\ell$: for $i=\ell ,\ell -1,\dots ,0$: take the smaller of the two split trees in $F_i$, raise all its level-$i$ tree edges to $i+1$, then scan its level-$i$ non-tree edges: one reaching the other side is the replacement (stop); one staying inside is raised to $i+1$.
• Query: same tree of $F_0$.

Proof sketch: $O({\log }^{2}n)$ amortised

Raising the smaller half keeps the size invariant: it has at most half of a component of size $\le n/2^i$. So levels never exceed $\log n$, and every scan that fails to find a replacement raises the scanned edge, which happens at most $\log n$ times per edge over its lifetime. Every raise or scan step costs $O(\log n)$ in the Euler tour trees. Hence $O({\log }^{2}n)$ amortised per update. Correctness: a replacement for a level-$\ell$ tree edge must have level $\le \ell$ (by the nesting invariant applied to the maximum-spanning-forest property with respect to levels), so scanning levels $\ell$ down to 0 finds one if it exists.

In contests, the offline method is almost always enough; HDT is worth knowing for online problems and for dynamic MST / 2-edge-connectivity extensions (which add more levels of bookkeeping — dynamic bipartiteness is the same level machinery with a parity bit per level instead of just a spanning forest). Frederickson’s earlier structure gets $O(\sqrt{m})$ worst-case (not just amortised) update time with a simpler sparsification-tree idea, predating HDT; HDT is asymptotically better and what’s actually implemented in practice.