Dynamic Connectivity

Maintain the connected components of a graph while edges are added and removed. The right technique depends entirely on which operations you need and whether the queries are known in advance.

The decision table

Operations	Technique	Complexity
Add edges only	DSU	$O(\alpha )$ amortized
Remove edges only	process in reverse with DSU	$O(\alpha )$ amortized
Add + remove, queries known in advance	segment tree on time + rollback DSU	$O((n+q)\log q\log n)$
Add + remove, online	HDT with Euler tour trees	$O({\log }^{2}n)$ amortized
Forest only (no cycles), online	link-cut trees	$O(\log n)$ amortized
Add + remove + MST	HDT extension	$O({\log }^{4}n)$

Almost always: go offline

Competitive programming problems give you the whole query list up front. That means the offline segment-tree technique applies, and it is dramatically easier than HDT.

Offline dynamic connectivity

The idea. Each edge is present during a set of time intervals. Build a segment tree over the time axis $[0,q)$ and insert each edge into the $O(\log q)$ nodes covering its lifetime. Then DFS the segment tree: on the way down, unite the edges stored at the node; on the way back up, roll those unions back. At a leaf, all currently-present edges are united, so answer that query.

struct RollbackDSU {
    vector<int> par, sz;
    vector<pair<int,int>> hist;              // (child root, its old parent)
    int comps;
    RollbackDSU(int n) : par(n), sz(n, 1), comps(n) { iota(par.begin(), par.end(), 0); }
 
    int find(int v) { while (par[v] != v) v = par[v]; return v; }   // NO path compression
 
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) { hist.push_back({-1, -1}); return; }
        if (sz[a] < sz[b]) swap(a, b);
        hist.push_back({b, a});
        par[b] = a; sz[a] += sz[b]; comps--;
    }
    void rollback() {
        auto [b, a] = hist.back(); hist.pop_back();
        if (b == -1) return;
        par[b] = b; sz[a] -= sz[b]; comps++;
    }
};
 
vector<vector<pair<int,int>>> seg;           // edges stored per segment tree node
 
void addEdge(int node, int l, int r, int ql, int qr, pair<int,int> e) {
    if (qr <= l || r <= ql) return;
    if (ql <= l && r <= qr) { seg[node].push_back(e); return; }
    int m = (l + r) / 2;
    addEdge(2*node, l, m, ql, qr, e);
    addEdge(2*node+1, m, r, ql, qr, e);
}
 
void solve(int node, int l, int r, RollbackDSU& dsu, vector<int>& ans) {
    int saved = dsu.hist.size();
    for (auto [u, v] : seg[node]) dsu.unite(u, v);
    if (r - l == 1) ans[l] = dsu.comps;
    else {
        int m = (l + r) / 2;
        solve(2*node, l, m, dsu, ans);
        solve(2*node+1, m, r, dsu, ans);
    }
    while ((int)dsu.hist.size() > saved) dsu.rollback();
}

No path compression

Rollback requires the DSU’s structure to be exactly restorable, so use union by size only. find becomes $O(\log n)$, which is where the extra log factor comes from. Attempting path compression with rollback silently corrupts the structure.

Computing edge lifetimes

Sweep the query list keeping a map from edge $\to$ the time it was added. On removal, record the interval $[\text{added},\text{now})$ and erase from the map. Edges still present at the end get $[\text{added},q)$.

map<pair<int,int>, int> alive;
for (int t = 0; t < q; t++) {
    if (type[t] == ADD)    alive[e[t]] = t;
    else if (type[t] == DEL) { addEdge(1, 0, q, alive[e[t]], t, e[t]); alive.erase(e[t]); }
}
for (auto [e, t] : alive) addEdge(1, 0, q, t, q, e);

What the leaves can answer

Anything a DSU can maintain rollback-ably:

• number of components,
• component sizes,
• “are $u$ and $v$ connected?”,
• bipartiteness (with a parity DSU),
• number of edges/cycles in each component,
• the maximum/minimum vertex label per component.

Path queries and MST maintenance need link-cut trees instead.

See also: DSU Variants · Link-Cut Trees · Offline Query Processing