Why this matters when you build with AI
Ask an AI tool for a disjoint set union (DSU) that can undo its last changes and you will often get a DSU with path compression. Path compression is a speed trick that rewrites parent pointers during find. It is correct for a plain DSU, and it breaks an undo. The code still runs and still prints an answer, so the error is easy to miss.
We ran both versions on a six-operation input in this lesson. The correct version printed yes and no. The version with path compression printed yes and yes. The second answer is wrong, and nothing warns you.
You catch this with a brute force. For each query, build a fresh DSU from the edges that are alive at that moment, and compare. It is slow and obviously correct. Run it on many small random inputs, and compare it with the fast code. The stress test in this lesson does that.
A prompt that asks for the right thing, with the limits stated:
Write C++17 code for a DSU that supports unite, find and undo of the last k unions,
with no path compression. Vertices are 0 to n - 1, with n up to 200000. Explain why
path compression is not allowed, and state the time of find and of one undo.A good answer uses union by size, keeps a stack of the unions it made, and explains that path compression changes parent pointers that an undo cannot restore. The time for find is O(log n), and an undo is O(1) per union. Check each claim against the code, then run the brute force.
Terms used
- A disjoint set union (DSU, also called union-find) keeps vertices in groups.
find(x)returns the root (representative) of x's group, andunite(a, b)merges two groups. - Rollback means undoing unions, in the reverse order they were made.
- A checkpoint is a saved stack size. Rolling back to a checkpoint undoes every union made after it.
- Offline means all operations are read before any answer is computed. The solver can then plan the answers in any order.
- Dynamic connectivity is the problem where edges are added and removed over time, and a query asks whether two vertices are connected at that moment.
- A segment tree over time is a segment tree whose leaves are the query moments. An edge alive for a range of queries is stored in the few nodes that exactly cover that range.
- An alive interval
[l, r)is the range of query numbers at which an edge exists. It includes l and excludes r.
The idea: union by size, and a stack of changes
Why no path compression
Path compression rewrites p[x] for every vertex on a path during find. When the union that made the root is undone, those rewritten pointers are still there, and they point to a root that is no longer the root. Undo cannot restore them unless it logs every write, which costs too much.
Without path compression, a unite changes exactly one pointer: p[b] = a. So the undo needs to remember only the pair (a, b).
Why union by size keeps find fast
Union by size attaches the root of the smaller group under the root of the larger group. A vertex's depth (the number of parent steps to reach the root) increases only when its group is attached under another group of at least the same size. Then the group it belongs to at least doubles in size. A group cannot double more than log2 n times, so every depth is at most log2 n, and find takes O(log n) steps.
A worked example
Start with five vertices, each alone. Each line below is one call, with its effect on the stack of changes (the history).
unite(0, 1): sizes 1 and 1, so attach 1 under 0. history: (0,1) sz[0] = 2
unite(2, 3): sizes 1 and 1, so attach 3 under 2. history: (0,1) (2,3) sz[2] = 2
checkpoint = 2 (two unions so far)
unite(1, 3): find(1) = 0 (size 2), find(3) = 2 (size 2). Sizes are equal, so attach 2 under 0.
history: (0,1) (2,3) (0,2) sz[0] = 4
rollback(2): pop (0,2) only. Set p[2] = 2 and sz[0] = 2.
groups now: {0, 1} and {2, 3}. find(3) = 2, and 0 and 2 are different groups.The rollback restores the same state as before the third union, because the stack recorded exactly what the union changed.
Rollback DSU in C++17
The header below has the rollback DSU and the offline solver. The template flag Compress exists only to show the bug. Use RollbackDSU<false>.
#pragma once
#include <bits/stdc++.h>
using namespace std;
struct Op {
char type; // 'a' add edge, 'd' delete one copy of an edge, 'q' ask connected(u, v)
int u, v;
};
// Disjoint set union that can undo unions in reverse order.
// Compress = false is the correct version: no path compression, union by size.
// Compress = true is the buggy version used to show the failure.
template <bool Compress>
struct RollbackDSU {
vector<int> p, sz;
vector<pair<int, int>> history; // (root that kept the set, root that was attached)
explicit RollbackDSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) {
if constexpr (Compress) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
} else {
while (p[x] != x) x = p[x];
return x;
}
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
history.push_back({a, b});
return true;
}
size_t checkpoint() const { return history.size(); }
// Undo every union made after checkpoint cp.
void rollback(size_t cp) {
while (history.size() > cp) {
auto [a, b] = history.back();
history.pop_back();
p[b] = b;
sz[a] -= sz[b];
}
}
};
// Offline solver: the time axis is the list of asks. An edge that is alive for asks
// [l, r) goes into O(log Q) segment tree nodes covering that range. A DFS over the tree
// adds the edges of each node and rolls them back when it leaves the node.
template <class D>
struct OfflineSolver {
D dsu;
int Q;
vector<vector<pair<int, int>>> tree;
vector<pair<int, int>> asks;
vector<char> ans;
OfflineSolver(int n, int q) : dsu(n), Q(q), tree(4 * max(q, 1)), ans(q, 0) {}
void addRange(int node, int nl, int nr, int l, int r, int u, int v) {
if (r <= nl || nr <= l) return;
if (l <= nl && nr <= r) {
tree[node].push_back({u, v});
return;
}
int mid = (nl + nr) / 2;
addRange(2 * node, nl, mid, l, r, u, v);
addRange(2 * node + 1, mid, nr, l, r, u, v);
}
void dfs(int node, int nl, int nr) {
size_t cp = dsu.checkpoint();
for (auto [u, v] : tree[node]) dsu.unite(u, v);
if (nr - nl == 1) {
ans[nl] = dsu.find(asks[nl].first) == dsu.find(asks[nl].second);
} else {
int mid = (nl + nr) / 2;
dfs(2 * node, nl, mid);
dfs(2 * node + 1, mid, nr);
}
dsu.rollback(cp);
}
};
// Returns one answer (1 = connected, 0 = not) per ask, in input order.
template <class D>
vector<char> solve_offline(int n, const vector<Op>& ops) {
struct Interval {
int u, v, l, r;
};
vector<Interval> ivs;
vector<pair<int, int>> asks;
map<pair<int, int>, vector<int>> alive; // edge key -> start ask numbers of live copies
for (const Op& op : ops) {
if (op.type == 'q') {
asks.push_back({op.u, op.v});
continue;
}
pair<int, int> key{min(op.u, op.v), max(op.u, op.v)};
int now = asks.size();
if (op.type == 'a') {
alive[key].push_back(now);
} else {
int l = alive[key].back(); // remove the most recently added live copy
alive[key].pop_back();
if (l < now) ivs.push_back({key.first, key.second, l, now});
}
}
int Q = asks.size();
for (auto& [key, starts] : alive) {
for (int l : starts) {
if (l < Q) ivs.push_back({key.first, key.second, l, Q});
}
}
if (Q == 0) return {};
OfflineSolver<D> solver(n, Q);
solver.asks = asks;
for (const Interval& iv : ivs) {
solver.addRange(1, 0, Q, iv.l, iv.r, iv.u, iv.v);
}
solver.dfs(1, 0, Q);
return solver.ans;
}The rollback DSU itself is the first half. find walks up the parents. unite changes one pointer and pushes one entry on history. rollback(cp) pops entries until the stack is back to cp, and undoes each one in reverse order.
Offline dynamic connectivity by divide and conquer over time
The input is a list of operations: add u v puts an edge in, del u v removes one copy of it, and ask u v asks whether u and v are connected right now. We do not process the list in order. Instead, we first find, for every edge copy, the range of asks at which it is alive. Then a segment tree over the asks holds those edges.
Each asks number is a leaf of the tree. An edge alive for asks [l, r) goes into the O(log Q) nodes that exactly cover that range. The DFS walks from the root to the leaves. At each node it unites the edges stored there, and then it goes down into the children. When it comes back up, it rolls back those unions. At a leaf, the set of edges unioned along the path from the root is exactly the set of edges alive for that ask, so the answer is a find comparison.
A worked example with the input file in this lesson:
5 9
add 0 1
ask 0 2
add 1 2
ask 0 2
add 2 3
ask 0 3
del 1 2
ask 0 3
ask 3 4There are five asks, numbered 0 to 4. The edge intervals are:
edge 0-1: added before ask 0, never removed alive for asks [0, 5)
edge 1-2: added before ask 1, removed before ask 3 alive for asks [1, 3)
edge 2-3: added before ask 2, never removed alive for asks [2, 5)Walk the tree. The root covers asks [0, 5), so edge 0-1 is stored there. The DFS adds 0-1 and goes left to [0, 2), which stores nothing. Its leaf for ask 0 has only 0-1 alive, so 0 and 2 are not connected: no. The leaf for ask 1 has 1-2 added (it is stored at that leaf), so 0, 1 and 2 are connected: yes. Back at the root, the right child [2, 5) stores 2-3. Its leaf for ask 2 has 0-1, 2-3 and 1-2 alive, so 0 and 3 are connected: yes. Its leaf for ask 3 has 1-2 gone, so 0 and 3 are apart: no. Ask 4 asks about 3 and 4, which are apart: no.
The program prints the same answers:
no
yes
yes
no
noThe code for the program is the file below. It reads the operations from standard input.
#include "dyn.hpp"
// Reads: n m, then m lines of "add u v", "del u v" or "ask u v". Prints yes or no per ask.
int main() {
int n, m;
cin >> n >> m;
vector<Op> ops;
for (int i = 0; i < m; i++) {
string word;
int u, v;
cin >> word >> u >> v;
char t = word == "add" ? 'a' : word == "del" ? 'd' : 'q';
ops.push_back({t, u, v});
}
vector<char> ans = solve_offline<RollbackDSU<false>>(n, ops);
for (char c : ans) cout << (c ? "yes" : "no") << "\n";
return 0;
}The stress test compares the solver with a brute force. The brute force keeps the alive edges in a plain list and builds a fresh DSU for every ask. The random inputs are always valid: a del only removes an edge that is alive.
#include "dyn.hpp"
// Brute force: keep the live edges in a list, and run a fresh DSU for every ask.
vector<char> brute(int n, const vector<Op>& ops) {
vector<pair<int, int>> alive;
vector<char> out;
for (const Op& op : ops) {
pair<int, int> key{min(op.u, op.v), max(op.u, op.v)};
if (op.type == 'a') {
alive.push_back(key);
} else if (op.type == 'd') {
alive.erase(find(alive.begin(), alive.end(), key));
} else {
RollbackDSU<false> d(n);
for (auto [a, b] : alive) d.unite(a, b);
out.push_back(d.find(op.u) == d.find(op.v));
}
}
return out;
}
// Random valid operation list: deletes only remove an edge that is alive.
vector<Op> randomOps(mt19937& rng, int n, int len) {
vector<Op> ops;
vector<pair<int, int>> alive;
for (int i = 0; i < len; i++) {
int r = rng() % 10;
if (r < 4) {
int u = rng() % n, v = rng() % n;
alive.push_back({u, v});
ops.push_back({'a', u, v});
} else if (r < 6 && !alive.empty()) {
int k = rng() % alive.size();
auto [u, v] = alive[k];
alive.erase(alive.begin() + k);
ops.push_back({'d', u, v});
} else {
ops.push_back({'q', (int)(rng() % n), (int)(rng() % n)});
}
}
return ops;
}
int main() {
mt19937 rng(777);
const int trials = 4000;
int goodFail = 0, badFail = 0, asksTotal = 0, yesCount = 0;
vector<Op> firstBadOps;
int firstBadN = 0;
for (int t = 0; t < trials; t++) {
int n = 1 + rng() % 7;
int len = 1 + rng() % 40;
vector<Op> ops = randomOps(rng, n, len);
vector<char> want = brute(n, ops);
vector<char> got = solve_offline<RollbackDSU<false>>(n, ops);
vector<char> gotBad = solve_offline<RollbackDSU<true>>(n, ops);
asksTotal += want.size();
for (char c : want) yesCount += c;
if (got != want) goodFail++;
if (gotBad != want) {
badFail++;
if (firstBadOps.empty() || ops.size() < firstBadOps.size()) {
firstBadOps = ops;
firstBadN = n;
}
}
}
cout << "correct rollback DSU: trials=" << trials << " asks=" << asksTotal
<< " answers yes=" << yesCount << " mismatches=" << goodFail << "\n";
cout << "buggy path-compression DSU: mismatches=" << badFail << " of " << trials << "\n";
if (!firstBadOps.empty()) {
cout << "shortest failing input has n=" << firstBadN << " and " << firstBadOps.size() << " ops\n";
}
return goodFail == 0 ? 0 : 1;
}The stress test printed this on the test machine (g++ 15.2.0 with -O2, on WSL2). The generator is seeded, so the counts should match on any machine with a standard C++17 compiler.
correct rollback DSU: trials=4000 asks=36110 answers yes=21396 mismatches=0
buggy path-compression DSU: mismatches=42 of 4000
shortest failing input has n=6 and 21 opsAmong the 42 failing inputs, the shortest had 21 operations. A separate search over inputs with 2 to 5 vertices and at most 10 operations found the 6-operation input shown in the common mistakes section. A search finds a witness, not a proof that no shorter failure exists.
Time on a larger input. We generated 200000 operations on 200000 vertices with about 40 percent adds, 20 percent deletes and the rest asks. The run took 0.24 seconds on the test machine. Almost every answer was no, because a sparse random graph is rarely connected, so this timing says little about how well the answers were checked. Your timings will differ with the machine.
Complexity
findcosts O(log n), because union by size keeps depth at most log2 n.unitecosts onefindper side plus O(1).rollbackcosts O(1) per undone union.- In the offline solver, each edge interval goes into at most about 2 log Q nodes, and each node unites its edges. The total time is O(E log Q log n), where E is the number of edge intervals, which is at most the number of adds. Each ask is answered at a leaf in O(log n).
- Memory: the segment tree stores O(E log Q) pairs.
Hands-on exercise
Do this on your own machine.
- Make a folder. Save the header above as
dyn.hpp, the main program asdyn_main.cpp, and the stress test asdyn_stress.cpp. Compile withg++ -std=c++17 -O2 -Wall -Wextra -o dyn_stress dyn_stress.cppand run./dyn_stress. The first line should showmismatches=0. - Save the example input from this lesson as
example.txt, and run./dyn_main < example.txt. Check the five answers by hand against the worked example. - Break the rollback on purpose. In
dyn.hpp, delete the linedsu.rollback(cp);indfs. Compile and run the stress test again. In our run, the correct-version line printedmismatches=957. Explain in one sentence what goes wrong: the unions from one tree node stay in place when the DFS moves to a sibling. - Restore the line. Make the stored interval one ask too long, by changing
nowtonow + 1in thedelbranch ofsolve_offline. Run./dyn_main < example.txtagain. In our run the fourth answer becameyesinstead ofno. Work out why, from the interval for edge 1-2. - Write a
RollbackDSUwith path halving (p[x] = p[p[x]]) infind. Run the stress test. Expect failures, and explain why in your own words before you look at the answer below.
Common mistakes
- Path compression in
find. The symptom is a wrongyeson a small input. Our six-operation example printedyesandyes. The correct output isyesandno. The stress test showed 42 failures out of 4000 inputs. - Forgetting to roll back in the DFS. Answers from one part of the segment tree leak into the next. The stress test showed 957 failures out of 4000 inputs when the rollback line was removed.
- Undoing unions out of order. Rollback must pop the stack in reverse. Any other order leaves the parent pointers in a state that matches no real history.
- Off-by-one on the interval end. Intervals are half-open:
[l, r)includes l and excludes r. If you store r inclusively, the edge stays alive one ask too long. In our test the fourth answer becameyesinstead ofno. - Deleting the wrong copy. If the same pair is added twice, a
delremoves one copy, not both. The code keeps a stack of start times per pair, so the most recent copy is removed first. Removing all copies gives wrong answers when a pair is added twice. - A
delfor an edge that is not alive. The input is invalid.alive[key].back()on an empty list is undefined behaviour, which can crash. Check the input before the solver runs. - Self-loops are harmless here, because
unite(v, v)returns false. Do not special-case them in a way that changes the answer. - Using a fresh DSU for each query. It is correct, as the brute force shows, but its time grows with the number of asks times the number of edges. Use it only as the check.
The six-operation input for the path compression bug:
4 6
add 2 0
add 1 3
add 3 0
ask 3 1
del 3 0
ask 3 2The correct version prints yes and no. The version with RollbackDSU<true> in the same main program prints yes and yes. After the del 3 0 line, only the edges 2-0 and 1-3 are alive, so vertices 3 and 2 are apart.
Checklist
finddoes not compress paths, andunitepushes exactly one entry on the stack.- Each unite that succeeds is undone by a rollback to the checkpoint taken before it.
- Rollback pops the stack in reverse order, down to the checkpoint.
- Intervals are half-open
[l, r)over ask numbers. - Every
delmatches an alive copy, and invalid input is rejected before the solver runs. - The solver gives the same answers as the brute force on many small random inputs, including inputs with repeated pairs and self-loops.
Summary
A rollback DSU trades path compression for an undo stack, and union by size keeps find fast without compression. Offline dynamic connectivity turns edge lifetimes into intervals over the ask numbers, and a segment tree over those numbers lets a DFS add each edge once per covering node and undo it on the way back. Each rule here was checked against the brute force, and the buggy variants show the symptoms to look for.
Practice problems
Practice 1: rollback by hand
Start with five vertices, each alone. Make these unions in order: unite(0, 1), unite(1, 2), unite(3, 4), unite(2, 4). Take a checkpoint after the third union, then make the fourth union. Roll back to the checkpoint. Which groups exist, and what does find(4) return? Use union by size with ties going to the first argument's root, as in the header.
Hint: write the history stack after each union. Rollback pops the entries above the checkpoint.
Show the answer
After unite(0, 1): p[1] = 0, sz[0] = 2, history (0,1). After unite(1, 2): find(1) = 0 (size 2), find(2) = 2 (size 1), so p[2] = 0, sz[0] = 3, history (0,1) (0,2). After unite(3, 4): p[4] = 3, sz[3] = 2, history (0,1) (0,2) (3,4). The checkpoint is 3. After unite(2, 4): find(2) = 0 (size 3), find(4) = 3 (size 2), so p[3] = 0, sz[0] = 5, history adds (0,3). Rollback to 3 pops (0,3): p[3] = 3, sz[0] = 3.
Groups: and . find(4) returns 3.
Practice 2: intervals from a short input
For this input, list the alive interval of each edge copy and the expected answers.
4 4
add 0 1
ask 0 1
del 0 1
ask 0 1Hint: count the asks before each operation. An edge added when k asks have happened starts at ask k.
Show the answer
The edge 0-1 is added when zero asks have happened, so it starts at ask 0. It is deleted after one ask, so its interval is [0, 1). Ask 0 sees the edge, so the answer is yes. Ask 1 does not, so the answer is no.
Output:
yes
noPractice 3: why depth is at most log2 n
Explain in a few sentences why union by size keeps the depth of every vertex at most log2 n, with no path compression.
Hint: consider what happens to a vertex's group size when its root is attached under another root.
Show the answer
A vertex's depth grows by one only when its root is attached under another root. Union by size attaches the smaller group under the larger one, so the group that contains the vertex at least doubles in size each time its depth grows. A group of n vertices can double at most log2 n times, because doubling from 1 reaches n after log2 n steps. So no vertex is deeper than log2 n, and find takes at most that many steps.
Practice 4: find the bug
A student adds path halving to find in the rollback DSU, using p[x] = p[p[x]] in a loop. Does rollback still restore the state? Explain.
Hint: ask which parent pointers rollback resets, and which parent pointers path halving changes.
Show the answer
No. Rollback resets only p[b] for the attached root b. Path halving also rewrites p[x] for vertices x on the path, which are not recorded anywhere. After an undo, such a vertex can still point past the root it used to belong to, so find gives wrong groups. The symptoms are the same as with full path compression: wrong yes answers on small inputs.
Practice 5: count the unions
For an input with E edge intervals and Q asks, give a bound on the number of unite calls that the offline solver makes, in big-O notation.
Hint: an interval is split into at most about 2 log Q segment tree nodes.
Show the answer
Each interval goes into O(log Q) nodes, so there are O(E log Q) stored pairs in total. The DFS calls unite once for each stored pair, and each call costs O(log n) for its two find calls. The total is O(E log Q log n) for the unions. The rollbacks cost the same number of undo steps, so the total stays O(E log Q log n).