Disjoint Set Union (DSU) Rollback - Preparation to IOI Part 3
Disjoint Set Union (DSU) Rollback
Disjoint Set Union (DSU) Rollback
Introduction
A normal DSU is very good when the graph only gets new edges. We can add an edge with union_sets(u, v), and then quickly check whether two vertices are in the same connected component.
But there is one important problem: DSU does not know how to delete an edge. If we once merge two components, the usual DSU cannot split them back. This is why dynamic connectivity with edge removals needs a different idea.
In this lecture, we study DSU rollback. The main idea is simple: we do not try to delete edges directly. Instead, we solve the problem offline, go through time using recursion, and after leaving a recursive part we undo the DSU changes we made there.
By the end, students should understand three ideas:
how to make DSU undo its last merges,
why we should not use path compression in rollback DSU,
how a segment tree over time turns edge add/remove operations into ordinary DSU merges.
Problem or motivation
We have an undirected graph with n vertices. Initially there are no edges.
There are q operations:
+ u v — add edge (u,v),
- u v — remove edge ,
(u,v)
? u v — ask whether u and v are currently connected.
For every query, print YES if the two vertices are connected at that moment, otherwise print NO.
To keep the first version clean, assume an edge is not added twice before being removed, and an edge is not removed when it is not active.
Example:
The answers are:
At time 2, edge (1,2) exists. At time 4, edges (1,2) and (2,3) exist, so 1 and 3 are connected. At time 6, edge (2,3) was removed, so 1 and 3 are no longer connected.
Naive approach
The most direct solution is to store the current set of edges. When we get + u v, we add the edge. When we get - u v, we remove it.
For every query ? u v, we run DFS or BFS in the current graph and check whether we can reach v from u.
This works, but it is too slow. In the worst case, one query can look through almost all vertices and edges. If there are many queries, the complexity can become about O(q(n+q)), which is too much for q up to 2⋅105.
A normal DSU also does not solve the problem. It can answer connectivity quickly after adding edges, but after removing an edge it cannot split a component. For example, after adding (1,2) and (2,3), DSU thinks 1,2,3 are one component. If we remove (2,3), the component should split, but normal DSU has no operation for that.
So we need a way to use DSU, but still handle removals.
Core concept
The key trick is to solve the problem offline. Offline means we first read all operations, and only then process them. Since we know the whole future, every edge has an active time interval.
For example, if edge (2,3) is added at time 3 and removed at time 5, then it is active on times 3 and 4. Its interval is [3,4].
If an edge is added and never removed, it is active until the end, so its interval is [start,q].
Now the problem becomes:
each edge is active on some interval of time,
for every query time, we need all edges whose interval contains that time.
To process these intervals efficiently, we build a segment tree over time positions 1,2,…,q. We add every edge interval into this segment tree. Then we run DFS over the segment tree:
when we enter a segment tree node, we add all edges stored in this node to DSU,
when we reach a leaf, we answer the query for that exact time,
when we leave the node, we rollback DSU to the state it had before entering the node.
This works because every edge stored in a segment tree node is active for the whole time segment of that node.
DSU rollback
Rollback DSU is a normal DSU that can return to an older state. The idea is very simple: before changing a variable, save its old value.
In one successful merge, we usually change three things:
cnt, the number of connected components,
p[X], because one root becomes a child of another root,
s[Y], because the new root gets a larger component size.
So before changing them, we push their old values into a stack. In the implementation, the stack stores pairs (address, old_value). For example, before changing p[X], we save (&p[X], p[X]).
A snapshot is just the current size of this stack. If we later want to return to that snapshot, we pop changes from the stack and write the old values back.
One very important detail: rollback DSU should not use path compression. Path compression changes many parent pointers inside get, and then we would need to save all of those changes too. For rollback DSU, we keep get simple and use only union by size.
Main algorithm
First, read all operations. For every edge, remember the time when it became active. When we see its removal, we now know its whole active interval, so we add that interval to the segment tree over time.
After reading all operations, some edges may still be active. Their intervals continue until time q.
Then we run recursive DFS on the segment tree.
When standing at node [l, r] of the time segment tree:
Save a DSU snapshot.
Add all edges stored in this node using union_sets.
If this is a leaf, answer the query at time l if operation l is a query.
Otherwise, recurse into the left child and the right child.
Rollback DSU to the saved snapshot.
Algorithm:
Why is this fast?
Each edge interval is added to only O(logq) segment tree nodes. During DFS, every stored edge causes one DSU merge attempt.
With union by size and no path compression, find_set takes O(logn). The reason is simple: whenever a root becomes a child of another root, it is attached to a component with size at least as large as itself. So the component containing that root at least doubles. A size can double only O(logn) times before reaching n, therefore the parent chain has length at most O(logn).
So the total complexity is O(qlogqlogn), which is fast enough for typical constraints.
Implementation
Complexity
Building intervals:O(qlogq) because we use a map for active edges.
Adding intervals to segment tree:O(qlogq) intervals in total.
DSU work:O(qlogqlogn) because each stored edge does one merge attempt, and each find_set is O(logn) with union by size.
Memory:O(qlogq+n) for the segment tree edge lists and DSU arrays.
1. Read n and q.
2. For each operation time i from 1 to q:
1. Read operation type and vertices u, v.
2. Normalize the edge so u <= v.
3. If operation is '+':
1. Remember that this edge started at time i.
4. If operation is '-':
1. Let start be the time when this edge was added.
2. Add this edge to the segment tree over interval [start, i - 1].
3. Remove this edge from the active map.
5. If operation is '?':
1. Store this query at time i.
3. For every edge still active after all operations:
1. Add it to the segment tree over interval [start, q].
4. Start DFS from the root segment [1, q].
5. In solve(x, l, r):
1. Save snapshot = current rollback stack size.
2. For every edge in this segment tree node:
1. Merge its endpoints in DSU.
3. If l == r:
1. If operation l is '?', answer using DSU.
4. Otherwise:
1. Recurse to the left child.
2. Recurse to the right child.
5. Rollback DSU to snapshot.
#include <bits/stdc++.h>using namespace std;const int N = 200100;int n, q;char op[N];int A[N], B[N];string ans[N];vector<pair<int, int>> seg[4 * N];struct DSURollback{ int cnt; vector<int> p; vector<int> s; vector<pair<int*, int>> v; DSURollback(int n) : p(n + 1), s(n + 1, 1){ cnt = n; for(int i = 1; i <= n; i++){ p[i] = i;}} int get(int x){ if(p[x] == x){ return x;} return get(p[x]);} int snapshot(){ return(int)v.size();} bool same(int x, int y){ return get(x) == get(y);} bool make(int x, int y){ x = get(x); y = get(y); if(x == y){ return false;} if(s[x]> s[y]){ swap(x, y);} v.push_back({&cnt, cnt}); v.push_back({&p[x], p[x]}); v.push_back({&s[y], s[y]}); cnt -= 1; p[x] = y; s[y] += s[x]; return true;} void rollback(int k){ while((int)v.size()> k){ *v.back().first = v.back().second; v.pop_back();}}};pair<int, int> normalize_edge(int u, int v){ if(u > v){ swap(u, v);} return{u, v};}void add_edge(int x, int l, int r, int tl, int tr, pair<int, int> edge){ if(tl > tr){ return;} if(l == tl && r == tr){ seg[x].push_back(edge); return;} int m =(l + r) / 2; add_edge(x * 2, l, m, tl, min(m, tr), edge); add_edge(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, edge);}void solve(int x, int l, int r, DSURollback &dsu){ int k = dsu.snapshot(); for(auto[u, v] : seg[x]){ dsu.make(u, v);} if(l == r){ if(op[l] == '?'){ ans[l] = dsu.same(A[l], B[l]) ? "YES" : "NO";} dsu.rollback(k); return;} int m =(l + r) / 2; solve(x * 2, l, m, dsu); solve(x * 2 + 1, m + 1, r, dsu); dsu.rollback(k);}int main(){ cin >> n >> q; map<pair<int, int>, int> start; for(int i = 1; i <= q; i++){ cin >> op[i]>> A[i]>> B[i]; pair<int, int> edge = normalize_edge(A[i], B[i]); if(op[i] == '+'){ start[edge] = i;} else if(op[i] == '-'){ int l = start[edge]; int r = i - 1; add_edge(1, 1, q, l, r, edge); start.erase(edge);}} for(auto[edge, l] : start){ add_edge(1, 1, q, l, q, edge);} DSURollback dsu(n); solve(1, 1, q, dsu); for(int i = 1; i <= q; i++){ if(op[i] == '?'){ cout << ans[i]<< '\n';}} return 0;}