DSU Rollback
A union-find variant that can undo merges, which is the missing piece behind offline dynamic connectivity.
DSU Rollback
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Rollback DSU is the union-find structure for offline problems where merges must be undone later. The central design choice is deliberate:
Give up path compression so every merge changes only a constant amount of reversible state.
Problem-Driven Motivation
The canonical contest setting is dynamic connectivity:
edges are added and removed over time,
connectivity queries ask about specific times,
the online fully dynamic problem is hard, but the full event list is known offline.
Ordinary DSU handles edge additions perfectly, but once an edge becomes inactive, ordinary DSU has no clean undo. The rollback version is built specifically for the offline divide-and-conquer or segment-tree-over-time reduction.
Recognition Pattern
Rollback DSU is a strong fit when:
unions must later be undone,
the problem is offline,
recursion branches or time intervals each need their own reversible DSU state.
Typical signals are:
offline dynamic connectivity,
``apply these changes on an interval, recurse, then undo'',
component data that evolves over a segment tree on time.
Derivation
Ordinary DSU is fast because of path compression, but path compression is also exactly what makes undo hard: it changes many parent pointers at once.
So rollback DSU uses:
union by size or rank,
no path compression,
a history stack recording the old state of every successful merge.
Each successful union changes only:
one child's parent,
one root's size,
optionally the component counter.
That is a constant-sized record, so rollback is simply popping history entries until a saved snapshot size is restored.
Worked Problem
Problem.
Edges are active on time intervals. For many time points, answer whether two vertices are connected.
Why naive fails.
Rebuilding the graph and recomputing connectivity from scratch at every time point is far too slow.
Offline reduction.
Build a segment tree over time. If edge \(e\) is active on interval \([l,r]\), attach \(e\) to all segment-tree nodes whose time segments lie fully inside \([l,r]\).
DFS over time.
At one segment-tree node:
take a snapshot of the DSU history size,
unite all edges stored at that node,
recurse to children,
roll back to the snapshot before returning.
Why this works.
Every recursion path corresponds to one time point. Along that path, exactly the edges active at that time have been merged into the DSU.
Implementation Reasoning
The rollback interface should stay minimal:
findwithout compression,unite,snapshot,rollback(snapshot).The important invariant is:
Rolling back to a snapshot must restore the DSU to exactly the state it had when that snapshot was taken.
That is why every successful merge records the overwritten parent, overwritten size, and component-count effect.
Correctness Intuition
On the segment tree over time, entering a node means ``all edges attached here are active for every time in this whole interval.'' So it is safe to merge them before recursion. Rolling back after finishing that interval ensures sibling intervals do not inherit merges that should not exist there.
Complexity Analysis
With union by size and no path compression:
find: \(O(\log n)\) worst case,unite: \(O(\log n)\),rollback of one merge: \(O(1)\),
memory: \(O(n + \text{number of successful merges})\).
Common Pitfalls
Adding path compression and destroying reversibility.
Forgetting to take the snapshot before applying the interval's merges.
Recording too little history to restore the old state exactly.
Using rollback DSU on an online deletion problem where the full event timeline is not known.
Variants and Failure Modes
Additional component metadata such as parity or sums can be rolled back too.
Persistent DSU is a different idea: version access instead of explicit undo.
If the problem needs online edge deletions, rollback alone is not enough.
Practice Problems
Offline dynamic connectivity.
Offline bipartiteness under interval-active edges.
Divide-and-conquer-over-time problems with reversible component merges.
References
\href{https://cp-algorithms.com/data_structures/deleting_in_log_n.html}{cp-algorithms: Deleting from a Data Structure in \(O(T(n)\log n)\)}.
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct DsuRollback {
struct Change {
int child;
int parent_before;
int root;
int size_before;
};
vector<int> parent;
vector<int> size;
vector<Change> history;
int components;
explicit DsuRollback(int n) : parent(n), size(n, 1), components(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int v) const {
while (parent[v] != v) v = parent[v];
return v;
}
int snapshot() const {
return (int)history.size();
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (size[a] < size[b]) swap(a, b);
history.push_back({b, parent[b], a, size[a]});
parent[b] = a;
size[a] += size[b];
--components;
return true;
}
void rollback(int snap) {
while ((int)history.size() > snap) {
Change ch = history.back();
history.pop_back();
parent[ch.child] = ch.parent_before;
size[ch.root] = ch.size_before;
++components;
}
}
bool same(int a, int b) const {
return find(a) == find(b);
}
};
struct ConnectivityQuery {
int u;
int v;
int id;
};
struct OfflineDynamicConnectivity {
int q;
vector<vector<pair<int, int>>> edges_on_segment;
vector<vector<ConnectivityQuery>> queries_at_time;
explicit OfflineDynamicConnectivity(int q)
: q(q), edges_on_segment(4 * q), queries_at_time(q) {}
void add_edge_interval(int node, int l, int r, int ql, int qr, pair<int, int> edge) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
edges_on_segment[node].push_back(edge);
return;
}
int mid = (l + r) / 2;
add_edge_interval(node * 2, l, mid, ql, qr, edge);
add_edge_interval(node * 2 + 1, mid + 1, r, ql, qr, edge);
}
void add_edge_interval(int left_time, int right_time, int u, int v) {
add_edge_interval(1, 0, q - 1, left_time, right_time, {u, v});
}
void add_query(int time, int u, int v, int id) {
queries_at_time[time].push_back({u, v, id});
}
void dfs(int node, int l, int r, DsuRollback& dsu, vector<int>& answer) {
int snap = dsu.snapshot();
for (const auto& edge : edges_on_segment[node]) dsu.unite(edge.first, edge.second);
if (l == r) {
for (const auto& query : queries_at_time[l]) {
answer[query.id] = dsu.same(query.u, query.v);
}
} else {
int mid = (l + r) / 2;
dfs(node * 2, l, mid, dsu, answer);
dfs(node * 2 + 1, mid + 1, r, dsu, answer);
}
dsu.rollback(snap);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.