Chapter 8 · Data Structures on Trees
Disjoint Set Union (Union–Find)
Two heuristics, one inverse-Ackermann bound, and the offline tricks that make it a problem-solving tool rather than a data structure.
Maintain a partition of {0, …, n-1} under two operations: unite(a, b) (merge the two classes) and find(a) (return a representative of a's class). Nothing else is supported — that limitation is why it is O(α(n)) instead of O(log n).
struct DSU {
vector<int> par, sz;
DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }
int find(int v) { while (v != par[v]) v = par[v] = par[par[v]]; return v; } // path halving
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false; // already together: the useful return value
if (sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
};After any sequence of unions, the depth of every vertex is at most log2 n.
A vertex's depth increases only when its root becomes a child of another root, and by the size rule that can only happen when the other tree is at least as large — so the subtree containing v at least doubles each time v goes one level deeper. Starting at size 1, at most log2 n doublings fit inside n. ∎
Union by size (or rank) plus path compression gives O(α(n)) amortised per operation, where α is the inverse Ackermann function — at most 4 for n up to 265536.
The proof (Tarjan; and the simpler O((m+n)log^* n) version) charges the cost of each find walk to "how many times did this vertex's parent change" and uses the doubling argument above to bound it by log^* n, then a two-level partition of ranks improves log^* to α. In practice the two heuristics differ like this: without compression, adversarial unions build Θ(log n) chains; without union by size, compression alone is O((m+n)log n) amortised and can degrade badly on "union(0,1), union(1,2), union(2,3), …" with interleaved finds. Use both; they are one line each.
Path halving vs full compression
par[v] = par[par[v]] (halving, as above) is iterative, allocation-free and within a few percent of full two-pass compression — it is what you should type in a contest. Full compression recursively re-points every visited node; it wins when finds are extremely repeated, and it is the version to prove things about.
#Extensions that are each two lines
For divide-and-conquer over time ("edge active on interval [l, r]") you need undo: record (child, parent_size) on a stack and revert. Depth is still O(log n) from union-by-size only, so each operation is O(log n) and queries are O(log2 n) with segment-tree-over-time. Total O(m log m log n), and it is the standard answer to "offline dynamic connectivity".
struct RollbackDSU {
vector<int> par, sz; vector<tuple<int,int,int>> hist;
int find(int v) { while (par[v] != v) v = par[v]; return v; } // no compression!
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) { hist.emplace_back(-1, -1, -1); return false; }
if (sz[a] < sz[b]) swap(a, b);
hist.emplace_back(b, a, sz[a]);
par[b] = a; sz[a] += sz[b];
return true;
}
void rollback() { // undo one recorded step
auto [b, a, sza] = hist.back(); hist.pop_back();
if (b == -1) return;
par[b] = b; sz[a] = sza;
}
};Extra payloads
- size / sum / max / count per class: keep an array indexed by the root and merge on
unite— the pattern behind "largest connected component", "is this class all the same colour", bipartite-with-parity, - parity DSU (weighted DSU with d[x] ∈ {0,1} from parent): the 10-line solution to "constraints of the form x ⊕ y = c" (Matching Applications, 2-SAT for the harder version),
- DSU on successor lists:
nxt[i]skipping already-used positions — the "colour the first uncoloured position in [l,r]" trick, O(n α(n)) for m paint operations, - Kruskal: sorting edges and uniting is literally running a sequence of graph contractions (Contraction, Induction and Lifting, Minimum Spanning Tree).
Free mode: click any two vertices to union them. Toggle path compression off, then union 0–1, 1–2, 2–3 … and watch max depth grow while the finds get slower.