These are the notes for Competitive Programming episode 47, the third episode of the graphs section. A DSU (disjoint set union, union–find) can join groups but never split them. The original problem Road Works adds an undo button: "−" removes the newest road still standing. Rebuilding the DSU on every undo is correct but Time Limit Exceeded. Writing every change in a history stack (like a shopkeeper's ledger) lets us undo the last change, but path compression makes hidden changes and the answer turns wrong (YES NO instead of YES YES); dropping compression without a size rule builds chains 2 · 10^5 long (TLE again). Union by size (small under large) keeps every tree at most log₂ n deep, because a node only gets deeper when its group at least doubles: measured, 17 for 131,072 towns. A real bug (a union that changed nothing was not recorded) makes undo remove the wrong road. The same doubling idea then solves Family Colours (distinct colours in every subtree): pouring the child's set into the parent is TLE on a bamboo; swapping first so the smaller set is poured into the larger is O(n log² n). Both are checked with stress tests. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
A shopkeeper writes every sale in a ledger, one line per change: what changed and what it was before. When a customer returns the last item, he does not redo the whole day; he crosses out the last line. This works only because nothing ever changes "off the books". The DSU with rollback is that ledger: every unite changes exactly one parent pointer and one size, it is written on a stack, and undo pops it.
The second idea is about merging piles. If you have to combine a big stack of papers with a small one, you put the small one on top of the big one, not the other way round. Then every sheet that moves lands in a pile at least twice as big as the one it came from, so no sheet can move more than log₂ n times.
DSU in one minute
- Every group has a root (leader);
p[x]is x's parent, andp[root] = root. find(x)follows parents up to the root.aandbare in the same group exactly whenfind(a) == find(b).unite(a, b)points one root at the other.- Path compression: after
find, point every node on the path straight at the root. With union by size it gives almost-constant time per operation (inverse Ackermann).
Problem U1 · Road Works
(Written for this course, in the style of a Codeforces educational round problem.)
n towns, no roads at first. q operations:
+ a b: build a road between towns a and b;-: remove the newest road that is still standing (there is always one);? a b: printYESif a can reach b now, elseNO.
Constraints: 1 ≤ n, q ≤ 2 · 10^5.
| Input | Output |
|---|---|
5 8 / + 1 2 / + 2 3 / ? 1 3 / + 1 3 / - / ? 1 3 / - / ? 1 3 |
YES YES NO |
4 6 / + 1 2 / + 3 4 / + 1 3 / ? 4 1 / - / ? 4 3 |
YES YES |
2 3 / ? 1 2 / + 1 2 / ? 2 2 |
NO YES |
In sample 1 the road 1 3 changes nothing (1 and 3 are already connected through 2), so the first - removes it and 1 still reaches 3; the second - removes 2 3.
The obvious attempt: rebuild on every undo (TLE)
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p;
vector<pair<int, int>> roads; // roads still standing
DSU(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void link(int a, int b) { p[find(b)] = find(a); }
void unite(int a, int b) { roads.push_back({a, b}); link(a, b); }
void undo() {
roads.pop_back();
iota(p.begin(), p.end(), 0); // start again from nothing
for (auto [a, b] : roads) link(a, b);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
DSU d(n);
while (q--) {
char t;
cin >> t;
if (t == '+') { int a, b; cin >> a >> b; d.unite(a, b); }
else if (t == '-') d.undo();
else { int a, b; cin >> a >> b; cout << (d.find(a) == d.find(b) ? "YES" : "NO") << "\n"; }
}
}
YES
YES
NO
The worst case: 2 · 10^5 roads, then 10^5 times "remove the newest road, build it again, ask":
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p;
vector<pair<int, int>> roads; // roads still standing
DSU(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void link(int a, int b) { p[find(b)] = find(a); }
void unite(int a, int b) { roads.push_back({a, b}); link(a, b); }
void undo() {
roads.pop_back();
iota(p.begin(), p.end(), 0); // start again from nothing
for (auto [a, b] : roads) link(a, b);
}
};
int main() {
int n = 200000; // worst case, built here
DSU d(n);
for (int i = 1; i < n; i++) d.unite(i, i + 1);
int yes = 0;
for (int k = 0; k < 100000; k++) {
d.undo(); // remove the newest road
d.unite(n - 1, n); // and build it again
yes += d.find(1) == d.find(n);
}
cout << "YES answers: " << yes << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
Every undo rebuilds up to 2 · 10^5 roads: about 2 · 10^10 steps. O(q²).
Write every change down: the history stack
A unite changes exactly two numbers: p[b] (root b now points at root a) and sz[a]. Push the pair (b, a) on a stack. undo() pops it and restores both: p[b] = b, sz[a] -= sz[b]. Because the roads are removed newest-first (a stack, LIFO), the last change is always the one to cross out.
Why path compression breaks rollback
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist; // (attached root, its new parent)
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } // 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);
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
DSU d(n);
while (q--) {
char t;
cin >> t;
if (t == '+') { int a, b; cin >> a >> b; d.unite(a, b); }
else if (t == '-') d.undo();
else { int a, b; cin >> a >> b; cout << (d.find(a) == d.find(b) ? "YES" : "NO") << "\n"; }
}
}
YES
NO
After + 1 2, + 3 4, + 1 3, the tree is 4 → 3 → 1 (and 2 → 1). The question ? 4 1 runs find(4), and path compression quietly sets p[4] = 1. That change is not on the stack. Undoing + 1 3 resets p[3] = 3, but 4 still points at 1, so ? 4 3 sees roots 1 and 3 and prints NO, although the road 3–4 was never removed. Rollback and path compression cannot be combined.
Without compression, the size rule is essential
Without compression, find walks the whole path. If unite always hangs a under b, the roads 1–2, 2–3, 3–4, … build one long chain:
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p;
vector<pair<int, int>> hist; // (attached root, its new parent)
DSU(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; } // no compression
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) { hist.push_back({-1, -1}); return; }
p[a] = b; // a under b, always
hist.push_back({a, b});
}
void undo() {
auto [a, b] = hist.back();
hist.pop_back();
if (a != -1) p[a] = a;
}
};
int main() {
int n = 200000; // worst case, built here
DSU d(n);
for (int i = 1; i < n; i++) d.unite(i, i + 1);
int yes = 0;
for (int k = 0; k < 100000; k++) {
d.undo(); // remove the newest road
d.unite(n - 1, n); // and build it again
yes += d.find(1) == d.find(n);
}
cout << "YES answers: " << yes << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
Every find(1) walks 2 · 10^5 steps.
Union by size: small under large, depth ≤ log₂ n
Keep sz[root] = the size of the group and always hang the smaller root under the larger one.
Claim: no node is ever deeper than log₂ n. Proof: a node's depth grows by one only when its root is hung under another root, and that happens only when its group is the smaller one. Then the new group is at least twice the size of its old group. A group's size can double at most log₂ n times before it reaches n. ∎
So find is O(log n) without compression, and every unite is still exactly one parent change and one size change: easy to undo. (Union by rank, hanging the shallower tree under the deeper one, gives the same bound.) The worst case is merging equal halves again and again; measured:
#include <bits/stdc++.h>
using namespace std;
struct DSU { // union by size
vector<int> p, sz;
vector<pair<int, int>> hist; // (attached root, its new parent)
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; }
int depth(int x) { int k = 0; while (p[x] != x) x = p[x], k++; return k; }
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) { hist.push_back({-1, -1}); return; } // nothing changed: still record it
if (sz[a] < sz[b]) swap(a, b); // small under large
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
int n = 1 << 17; // 131072 towns
DSU d(n);
for (int len = 1; len < n; len *= 2) // merge equal halves: the worst case
for (int i = 1; i + len <= n; i += 2 * len) d.unite(i, i + len);
int worst = 0;
for (int v = 1; v <= n; v++) worst = max(worst, d.depth(v));
cout << "deepest node: " << worst << "\n";
}
deepest node: 17
17 = log₂ 131072.
The accepted rollback DSU
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist; // (attached root, its new parent)
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; } // no compression
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) { hist.push_back({-1, -1}); return; } // nothing changed: still record it
if (sz[a] < sz[b]) swap(a, b); // small under large
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
DSU d(n);
while (q--) {
char t;
cin >> t;
if (t == '+') { int a, b; cin >> a >> b; d.unite(a, b); }
else if (t == '-') d.undo();
else { int a, b; cin >> a >> b; cout << (d.find(a) == d.find(b) ? "YES" : "NO") << "\n"; }
}
}
YES
YES
NO
YES
YES
NO
YES
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist; // (attached root, its new parent)
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; } // no compression
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) { hist.push_back({-1, -1}); return; } // nothing changed: still record it
if (sz[a] < sz[b]) swap(a, b); // small under large
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
int n = 200000; // worst case, built here
DSU d(n);
for (int i = 1; i < n; i++) d.unite(i, i + 1);
int yes = 0;
for (int k = 0; k < 100000; k++) {
d.undo(); // remove the newest road
d.unite(n - 1, n); // and build it again
yes += d.find(1) == d.find(n);
}
cout << "YES answers: " << yes << "\n";
}
YES answers: 100000
The no-op union bug
"If a and b are already together nothing changed, so why write anything down?"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist; // (attached root, its new parent)
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; } // no compression
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return; // nothing changed
if (sz[a] < sz[b]) swap(a, b); // small under large
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
DSU d(n);
while (q--) {
char t;
cin >> t;
if (t == '+') { int a, b; cin >> a >> b; d.unite(a, b); }
else if (t == '-') d.undo();
else { int a, b; cin >> a >> b; cout << (d.find(a) == d.find(b) ? "YES" : "NO") << "\n"; }
}
}
YES
NO
NO
Expected YES YES NO. The road 1 3 changed nothing and was not recorded, so the next - popped the change made by 2 3 instead. Every + must push exactly one entry, even a marker (−1, −1) for "nothing changed".
Stress test against the rebuild
1000 random runs of 30 operations on up to 7 towns, the rollback DSU against the slow rebuild (only undoing when a road is standing):
#include <bits/stdc++.h>
using namespace std;
struct Slow {
vector<int> p;
vector<pair<int, int>> roads; // roads still standing
Slow(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void link(int a, int b) { p[find(b)] = find(a); }
void unite(int a, int b) { roads.push_back({a, b}); link(a, b); }
void undo() {
roads.pop_back();
iota(p.begin(), p.end(), 0); // start again from nothing
for (auto [a, b] : roads) link(a, b);
}
};
struct Fast {
vector<int> p, sz;
vector<pair<int, int>> hist; // (attached root, its new parent)
Fast(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; } // no compression
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) { hist.push_back({-1, -1}); return; } // nothing changed: still record it
if (sz[a] < sz[b]) swap(a, b); // small under large
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
mt19937 rng(47);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 6 + 2, built = 0;
Slow s(n);
Fast f(n);
for (int op = 0; op < 30; op++) {
int a = rng() % n + 1, b = rng() % n + 1, kind = rng() % 3;
if (kind == 0) { s.unite(a, b); f.unite(a, b); built++; }
else if (kind == 1 && built > 0) { s.undo(); f.undo(); built--; }
else if ((s.find(a) == s.find(b)) != (f.find(a) == f.find(b))) {
cout << "mismatch on test " << t;
return 0;
}
}
}
cout << "all 1000 tests passed";
}
all 1000 tests passed
Problem U2 · Family Colours
(Written for this course, in the style of a Codeforces Div. 2 D problem.)
A family tree of n people; person 1 is the root and for i ≥ 2 the parent of i is par_i < i. Person i's favourite colour is col_i. For every person v print the number of different colours in v's subtree (v and everyone below v).
- Input: n (1 ≤ n ≤ 2 · 10^5), then par_2 … par_n, then col_1 … col_n (1 ≤ col_i ≤ 10^9).
- Output: n numbers.
| Input | Output |
|---|---|
6 / 1 1 2 2 3 / 1 2 1 3 2 2 |
3 2 2 1 1 1 |
1 / (no parents) / 5 |
1 |
Because every parent has a smaller number than its children, processing v = n, n − 1, …, 1 handles all children before their parent, with no recursion at all (so no stack overflow on a bamboo).
The obvious attempt: pour each child's set into its parent (TLE)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> par(n + 1, 0), col(n + 1);
for (int i = 2; i <= n; i++) cin >> par[i]; // par[i] < i
for (int i = 1; i <= n; i++) cin >> col[i];
vector<set<int>> s(n + 1);
for (int v = 1; v <= n; v++) s[v].insert(col[v]);
vector<int> ans(n + 1);
for (int v = n; v >= 1; v--) { // children have bigger numbers: done first
ans[v] = s[v].size();
if (v == 1) break;
int p = par[v];
for (int x : s[v]) s[p].insert(x); // pour the child into the parent
s[v].clear();
}
for (int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
}
3 2 2 1 1 1
A bamboo (a path 1 – 2 – … – n) with all colours different:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 200000; // a bamboo: 1 - 2 - 3 - ... - n
vector<int> par(n + 1, 0), col(n + 1);
for (int i = 2; i <= n; i++) par[i] = i - 1;
for (int i = 1; i <= n; i++) col[i] = i; // all different
vector<set<int>> s(n + 1);
for (int v = 1; v <= n; v++) s[v].insert(col[v]);
vector<int> ans(n + 1);
for (int v = n; v >= 1; v--) { // children have bigger numbers: done first
ans[v] = s[v].size();
if (v == 1) break;
int p = par[v];
for (int x : s[v]) s[p].insert(x); // pour the child into the parent
s[v].clear();
}
cout << "colours under 1: " << ans[1] << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
The set at the bottom grows by one each step and is poured upward every time: 1 + 2 + … + n ≈ 2 · 10^10 inserts. The problem is the direction: we pour a large set into a small one.
Small to large
Before pouring, if (s[v].size() > s[p].size()) swap(s[v], s[p]);. Swapping two std::sets is O(1): only internal pointers move. Now a colour moves only out of the smaller set, into a set at least as big, so the set it ends up in is at least twice as big as the one it left: each colour moves at most log₂ n times, each move is one set insert (O(log n)), total O(n log² n). It is the same doubling argument as union by size. (With unordered_set, O(n log n) expected.)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> par(n + 1, 0), col(n + 1);
for (int i = 2; i <= n; i++) cin >> par[i]; // par[i] < i
for (int i = 1; i <= n; i++) cin >> col[i];
vector<set<int>> s(n + 1);
for (int v = 1; v <= n; v++) s[v].insert(col[v]);
vector<int> ans(n + 1);
for (int v = n; v >= 1; v--) { // children have bigger numbers: done first
ans[v] = s[v].size();
if (v == 1) break;
int p = par[v];
if (s[v].size() > s[p].size()) swap(s[v], s[p]); // O(1): small into large
for (int x : s[v]) s[p].insert(x);
s[v].clear();
}
for (int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
}
3 2 2 1 1 1
1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 200000; // a bamboo: 1 - 2 - 3 - ... - n
vector<int> par(n + 1, 0), col(n + 1);
for (int i = 2; i <= n; i++) par[i] = i - 1;
for (int i = 1; i <= n; i++) col[i] = i; // all different
vector<set<int>> s(n + 1);
for (int v = 1; v <= n; v++) s[v].insert(col[v]);
vector<int> ans(n + 1);
for (int v = n; v >= 1; v--) { // children have bigger numbers: done first
ans[v] = s[v].size();
if (v == 1) break;
int p = par[v];
if (s[v].size() > s[p].size()) swap(s[v], s[p]); // O(1): small into large
for (int x : s[v]) s[p].insert(x);
s[v].clear();
}
cout << "colours under 1: " << ans[1] << "\n";
}
colours under 1: 200000
Stress test against the plain version on 1000 random families:
#include <bits/stdc++.h>
using namespace std;
vector<int> solve(int n, vector<int> par, vector<int> col, bool swapSmall) {
vector<set<int>> s(n + 1);
for (int v = 1; v <= n; v++) s[v].insert(col[v]);
vector<int> ans(n + 1);
for (int v = n; v >= 1; v--) {
ans[v] = s[v].size();
if (v == 1) break;
int p = par[v];
if (swapSmall && s[v].size() > s[p].size()) swap(s[v], s[p]);
for (int x : s[v]) s[p].insert(x);
s[v].clear();
}
return ans;
}
int main() {
mt19937 rng(47);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 12 + 1;
vector<int> par(n + 1, 0), col(n + 1);
for (int i = 2; i <= n; i++) par[i] = rng() % (i - 1) + 1;
for (int i = 1; i <= n; i++) col[i] = rng() % 4 + 1;
if (solve(n, par, col, false) != solve(n, par, col, true)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
all 1000 tests passed
This technique is often called DSU on tree or small-to-large merging; the Sack (Arpa's trick) and heavy-child versions are refinements of the same idea.
Complexity vs the constraints
n, q ≤ 2 · 10^5.
| Method | Time | n = q = 2 · 10^5 |
|---|---|---|
| rebuild the DSU on every undo | O(q²) ≈ 2 · 10^10 | TLE |
| history stack + path compression | — | Wrong Answer |
| history stack, no compression, naive union | O(n) per find | TLE (chains) |
| rollback DSU, union by size | O(log n) per operation, ≈ 4 · 10^6 total | accepted, milliseconds |
| pour child set into parent | O(n²) worst case | TLE on a bamboo |
small to large (std::set) |
O(n log² n) ≈ 6 · 10^7 | accepted, 0.04 s |
Memory: O(n + q) for the DSU and its history; O(n) set entries in total at any time for small to large.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| rebuild the DSU on every undo | Time Limit Exceeded |
O(q) work per undo | history stack, undo the last change |
| path compression with rollback | YES NO (expected YES YES) |
compression changes parents off the stack | union by size only, no compression |
| no compression and no size rule | Time Limit Exceeded |
chains of length n | small under large |
| not recording a no-op union | YES NO NO (expected YES YES NO) |
undo pops the wrong change | push (−1, −1) |
forgetting sz[a] -= sz[b] in undo |
sizes wrong, depth bound lost, slow or WA | the ledger was only half restored | restore every changed field |
| pouring large into small | Time Limit Exceeded |
a big set moves again and again | swap first, then pour small into large |
| recursive DFS for subtree sets on a bamboo | Segmentation fault possible |
depth 2 · 10^5 | iterate v = n..1 (parents first numbered) or an explicit stack |
Mini project
Build a rollback DSU library: unite, undo, find, same(a, b), groups(), size(x), and snapshot() / rollbackTo(snapshot) (store hist.size(), pop until you are back there). Use it to solve Road Works, homework 1 and homework 2, and then the offline dynamic connectivity problem (homework 4), where a segment tree over time decides which roads are alive and the DSU is rolled back when the recursion leaves a node. Stress test each against a rebuild-from-scratch checker.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Count the groups. Road Works without ?: after every operation print the number of groups.
Solution
Keep groups in the DSU: a real union does groups--, its undo does groups++; a no-op changes nothing either way.
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist;
int groups;
DSU(int n) : p(n + 1), sz(n + 1, 1), groups(n) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; }
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);
p[b] = a;
sz[a] += sz[b];
groups--; // one group fewer
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
groups++; // undo it too
}
};
int main() {
int n, q;
cin >> n >> q;
DSU d(n);
while (q--) {
char t;
cin >> t;
if (t == '+') { int a, b; cin >> a >> b; d.unite(a, b); }
else d.undo();
cout << d.groups << "\n"; // after every operation
}
}
Input 4 5 / + 1 2 / + 3 4 / + 1 2 / - / -:
3
2
2
2
3
2. Undo k roads. - k removes the k newest roads still standing.
Solution
Pop k times. Each road is pushed once and popped at most once, so the total over all operations is still O(q log n) (amortised).
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; }
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);
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
int n, q;
cin >> n >> q;
DSU d(n);
while (q--) {
char t;
cin >> t;
if (t == '+') { int a, b; cin >> a >> b; d.unite(a, b); }
else if (t == '-') { int k; cin >> k; while (k--) d.undo(); } // each road is undone once: O(log n) amortised
else { int a, b; cin >> a >> b; cout << (d.find(a) == d.find(b) ? "YES" : "NO") << "\n"; }
}
}
Input 4 7 / + 1 2 / + 2 3 / + 3 4 / ? 1 4 / - 2 / ? 1 4 / ? 1 2:
YES
NO
YES
3. Most frequent colour. For every person, print the colour that appears most often in their subtree (the smallest colour on ties).
Solution
Small to large with a map<colour, count> per person and the current best (count, colour) next to it. When two maps are swapped, swap their "best" too; while pouring, every updated count can only grow, so comparing it with the best is enough. O(n log² n).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> par(n + 1, 0), col(n + 1);
for (int i = 2; i <= n; i++) cin >> par[i];
for (int i = 1; i <= n; i++) cin >> col[i];
vector<map<int, int>> cnt(n + 1); // colour -> how many in this subtree
vector<pair<int, int>> top(n + 1); // (best count, smallest colour with it)
auto better = [](pair<int, int> a, pair<int, int> b) { // more often, then smaller colour
return a.first != b.first ? a.first > b.first : a.second < b.second;
};
for (int v = 1; v <= n; v++) { cnt[v][col[v]] = 1; top[v] = {1, col[v]}; }
vector<int> ans(n + 1);
for (int v = n; v >= 1; v--) {
ans[v] = top[v].second;
if (v == 1) break;
int p = par[v];
if (cnt[v].size() > cnt[p].size()) { swap(cnt[v], cnt[p]); swap(top[v], top[p]); }
for (auto [c, k] : cnt[v]) { // pour the smaller map into the larger
int now = cnt[p][c] += k;
if (better({now, c}, top[p])) top[p] = {now, c};
}
cnt[v].clear();
}
for (int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
}
The episode's sample, and 5 / 1 1 2 2 / 4 4 7 4 7:
2 2 1 3 2 2
4 4 7 4 7
4. Roads with a time window (offline dynamic connectivity). Operations + a b (build), x a b (destroy an existing road, any one, not only the newest) and ? a b. All operations are known in advance.
Solution
Each road is alive during one interval of operation times [built, destroyed − 1]. Build a segment tree over time and add each road to the O(log q) tree nodes that cover its interval. A DFS over the segment tree unites the roads of a node when it enters, answers the questions at the leaves, and rolls back those unions when it leaves. Each road is united O(log q) times, each union O(log n): O(q log q log n). Rollback is what makes this work: undo order is exactly the reverse of the DFS order.
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; }
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);
p[b] = a; sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back(); hist.pop_back();
if (b == -1) return;
p[b] = b; sz[a] -= sz[b];
}
};
int n, q;
vector<vector<pair<int, int>>> seg; // roads alive on a whole node's time range
vector<array<int, 3>> asks; // (time, a, b) for '?'
vector<string> out;
void add(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 mid = (l + r) / 2;
add(2 * node, l, mid, ql, qr, e);
add(2 * node + 1, mid + 1, r, ql, qr, e);
}
void solve(int node, int l, int r, DSU &d, vector<int> &askAt) {
for (auto [a, b] : seg[node]) d.unite(a, b);
if (l == r) {
if (askAt[l] != -1) { auto [t, a, b] = asks[askAt[l]]; out[askAt[l]] = d.find(a) == d.find(b) ? "YES" : "NO"; }
} else {
int mid = (l + r) / 2;
solve(2 * node, l, mid, d, askAt);
solve(2 * node + 1, mid + 1, r, d, askAt);
}
for (size_t i = 0; i < seg[node].size(); i++) d.undo(); // leave the node: roll back
}
int main() {
cin >> n >> q; // ops: "+ a b" build, "x a b" destroy, "? a b"
seg.assign(4 * q + 4, {});
map<pair<int, int>, int> openSince;
vector<int> askAt(q, -1);
for (int t = 0; t < q; t++) {
char c; int a, b;
cin >> c >> a >> b;
if (a > b) swap(a, b);
if (c == '+') openSince[{a, b}] = t;
else if (c == 'x') { add(1, 0, q - 1, openSince[{a, b}], t - 1, {a, b}); openSince.erase({a, b}); }
else { askAt[t] = asks.size(); asks.push_back({t, a, b}); }
}
for (auto [e, t] : openSince) add(1, 0, q - 1, t, q - 1, e); // still standing at the end
out.assign(asks.size(), "");
DSU d(n);
solve(1, 0, q - 1, d, askAt);
for (auto &s : out) cout << s << "\n";
}
Input 4 8 / + 1 2 / + 2 3 / ? 1 3 / x 1 2 / ? 1 3 / + 1 3 / ? 1 2 / ? 3 4:
YES
NO
YES
NO
Quick quiz
Union by size, no path compression, 1024 towns. How deep can the deepest node be?
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
A) 1 · B) 10 · C) 32 · D) 1023
Answer
B. Each step deeper at least doubles the node's group, and a group can double only log₂ 1024 = 10 times. Merging equal halves again and again reaches exactly 10.
Interview questions
- What is a DSU and what are its operations? A structure for disjoint groups:
find(x)returns x's group root,unite(a, b)merges two groups. With path compression and union by size, almost O(1) per operation. - How do you support undo? Union by size without path compression, and a stack of changes (the attached root and its new parent). Undo pops one entry and restores the parent and the size. O(log n) per find.
- Why can't you use path compression with rollback? Compression rewrites many parents during
find, and those changes are not recorded, so undoing a union leaves stale pointers into the removed group. - Why is union by size O(log n) deep? A node gets deeper only when its group is merged under one at least as large, which at least doubles the group size; that can happen at most log₂ n times.
- What is small-to-large merging? When merging two collections, insert the elements of the smaller into the larger. Each element moves O(log n) times, so merging everything costs O(n log n) moves.
- Where is rollback used? Offline dynamic connectivity (segment tree over time), divide and conquer on queries, Mo's algorithm with a DSU, backtracking searches that try a union and undo it.
Glossary
| Term | Meaning | Example |
|---|---|---|
| DSU (disjoint set union, union–find) | A structure that keeps disjoint groups and can merge them | towns joined by roads |
| Root (leader) | The node that represents a group; p[root] = root |
find(4) = 1 |
| Parent array | p[x] = the next node on the way to the root |
p[4] = 3 |
find |
Follow parents up to the root | while (p[x] != x) x = p[x]; |
unite |
Merge two groups by pointing one root at the other | p[b] = a |
| Path compression | Pointing every node on a find path straight at the root | p[x] = find(p[x]) |
| Union by size | Hanging the smaller group's root under the larger one's | if (sz[a] < sz[b]) swap(a, b); |
| Union by rank | The same idea using tree height instead of size | depth ≤ log₂ n |
| Depth | The number of parent steps from a node to its root | 17 for 131,072 towns |
| Rollback (undo) | Reversing the most recent change | p[b] = b; sz[a] -= sz[b]; |
| History stack | The list of changes, newest last, so they can be undone in reverse order | vector<pair<int, int>> hist |
| Stack (LIFO) | Last in, first out | the newest road is removed first |
| No-op union | A unite of two nodes already in the same group | + 1 3 after 1 2 and 2 3 |
| Marker entry | A placeholder pushed for a no-op so pushes and pops stay matched | {-1, -1} |
| Amortised | A bound on a whole sequence of operations, even if one is expensive | undo k roads at once |
| Chain | A tree shaped like a line; the worst case for find |
1 → 2 → 3 → … → n |
| Doubling argument | "Each time X happens, a size at least doubles, so X happens ≤ log₂ n times" | union by size, small to large |
| Subtree | A node and all its descendants | the branch under person 2 |
| Bamboo | A tree that is a single path | par[i] = i − 1 |
| Small to large | Always merge the smaller collection into the larger | swap, then pour |
swap of containers |
O(1): exchanges the internal pointers, not the elements | swap(s[v], s[p]) |
std::set |
A sorted container of distinct values, O(log n) insert | colours in a subtree |
std::map |
A sorted key → value container | colour → count |
| DSU on tree (Sack) | Small-to-large applied to subtree statistics | Family Colours |
| Offline | All queries are known before answering | dynamic connectivity homework |
| Segment tree over time | A segment tree whose positions are operation times | roads alive on an interval |
| Stress test | Comparing a fast solution with a slow, surely-correct one on random inputs | all 1000 tests passed |
iota |
Fills a range with 0, 1, 2, … | iota(p.begin(), p.end(), 0) |
| Time Limit Exceeded / Wrong Answer | Judge verdicts for too slow / wrong output | rebuild: TLE; compression: WA |
Summary
- A DSU can join but not split. Rebuilding on undo is O(q²): TLE.
- Write every change on a history stack and undo the last one: one parent and one size.
- Path compression makes unrecorded changes:
YES NOinstead ofYES YES. Use no compression. - Without compression, union by size is essential: depth ≤ log₂ n (measured 17 for 131,072), O(log n) per operation; the naive union makes chains (TLE).
- Record a no-op union too, or undo removes the wrong road (
YES NO NO). - Small to large: swap so the smaller set is poured into the larger; each element moves ≤ log₂ n times: O(n log² n),
200000colours on a bamboo in 0.04 s. Same doubling idea.
Solutions in C++, Java and Python
Problem U1 · Road Works
C++
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
vector<pair<int, int>> hist; // (attached root, its new parent)
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (p[x] != x) x = p[x]; return x; } // no compression
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) { hist.push_back({-1, -1}); return; } // nothing changed: still record it
if (sz[a] < sz[b]) swap(a, b); // small under large
p[b] = a;
sz[a] += sz[b];
hist.push_back({b, a});
}
void undo() {
auto [b, a] = hist.back();
hist.pop_back();
if (b == -1) return;
p[b] = b;
sz[a] -= sz[b];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
DSU d(n);
while (q--) {
char t;
cin >> t;
if (t == '+') { int a, b; cin >> a >> b; d.unite(a, b); }
else if (t == '-') d.undo();
else { int a, b; cin >> a >> b; cout << (d.find(a) == d.find(b) ? "YES" : "NO") << "\n"; }
}
}
Java
import java.io.*;
import java.util.*;
public class Main {
static int[] p, sz;
static int[] histB, histA; // the history stack as two arrays
static int top = 0;
static int find(int x) { while (p[x] != x) x = p[x]; return x; } // no compression
static void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) { histB[top] = -1; histA[top++] = -1; return; } // record a no-op too
if (sz[a] < sz[b]) { int t = a; a = b; b = t; } // small under large
p[b] = a; sz[a] += sz[b];
histB[top] = b; histA[top++] = a;
}
static void undo() {
top--;
int b = histB[top], a = histA[top];
if (b == -1) return;
p[b] = b; sz[a] -= sz[b];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());
p = new int[n + 1]; sz = new int[n + 1];
for (int i = 0; i <= n; i++) { p[i] = i; sz[i] = 1; }
histB = new int[q]; histA = new int[q];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
String t = st.nextToken();
if (t.equals("+")) unite(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
else if (t.equals("-")) undo();
else {
int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
sb.append(find(a) == find(b) ? "YES" : "NO").append('\n');
}
}
System.out.print(sb);
}
}
YES
YES
NO
YES
YES
NO
YES
Python
import sys
def main():
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
p = list(range(n + 1))
sz = [1] * (n + 1)
hist = [] # (attached root, its new parent) or (-1, -1)
def find(x):
while p[x] != x: # no path compression
x = p[x]
return x
out = []
i = 2
for _ in range(q):
t = data[i]; i += 1
if t == '+':
a, b = find(int(data[i])), find(int(data[i + 1])); i += 2
if a == b:
hist.append((-1, -1)) # record a no-op too
continue
if sz[a] < sz[b]:
a, b = b, a # small under large
p[b] = a
sz[a] += sz[b]
hist.append((b, a))
elif t == '-':
b, a = hist.pop()
if b != -1:
p[b] = b
sz[a] -= sz[b]
else:
a, b = int(data[i]), int(data[i + 1]); i += 2
out.append("YES" if find(a) == find(b) else "NO")
print("\n".join(out))
main()
YES
YES
NO
YES
YES
NO
YES
Problem U2 · Family Colours
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> par(n + 1, 0), col(n + 1);
for (int i = 2; i <= n; i++) cin >> par[i]; // par[i] < i
for (int i = 1; i <= n; i++) cin >> col[i];
vector<set<int>> s(n + 1);
for (int v = 1; v <= n; v++) s[v].insert(col[v]);
vector<int> ans(n + 1);
for (int v = n; v >= 1; v--) { // children have bigger numbers: done first
ans[v] = s[v].size();
if (v == 1) break;
int p = par[v];
if (s[v].size() > s[p].size()) swap(s[v], s[p]); // O(1): small into large
for (int x : s[v]) s[p].insert(x);
s[v].clear();
}
for (int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
}
Java (HashSet: expected O(1) inserts, so O(n log n) expected)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
int[] par = new int[n + 1], col = new int[n + 1];
for (int i = 2; i <= n; i++) { st.nextToken(); par[i] = (int) st.nval; }
for (int i = 1; i <= n; i++) { st.nextToken(); col[i] = (int) st.nval; }
List<HashSet<Integer>> s = new ArrayList<>();
s.add(null);
for (int v = 1; v <= n; v++) { HashSet<Integer> h = new HashSet<>(); h.add(col[v]); s.add(h); }
int[] ans = new int[n + 1];
for (int v = n; v >= 1; v--) {
ans[v] = s.get(v).size();
if (v == 1) break;
int p = par[v];
if (s.get(v).size() > s.get(p).size()) { // swap the references: O(1)
HashSet<Integer> t = s.get(v); s.set(v, s.get(p)); s.set(p, t);
}
s.get(p).addAll(s.get(v)); // small into large
s.set(v, null);
}
StringBuilder sb = new StringBuilder();
for (int v = 1; v <= n; v++) sb.append(ans[v]).append(v == n ? "\n" : " ");
System.out.print(sb);
}
}
3 2 2 1 1 1
1
Python (set, the |= operator pours the smaller set into the larger)
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
par = [0, 0] + [int(x) for x in data[1:n]]
col = [0] + [int(x) for x in data[n:2 * n]]
s = [None] + [{col[v]} for v in range(1, n + 1)]
ans = [0] * (n + 1)
for v in range(n, 0, -1): # children have bigger numbers: done first
ans[v] = len(s[v])
if v == 1:
break
p = par[v]
if len(s[v]) > len(s[p]):
s[v], s[p] = s[p], s[v] # swap references: O(1)
s[p] |= s[v] # small into large
s[v] = None
print(' '.join(map(str, ans[1:])))
main()
3 2 2 1 1 1
1