Disjoint Set Union in C++: Union by Size, Path Compression
DSU (union-find) in C++ for contests: a parent array, find with path compression, union by size, and the near-O(1) cost that makes connectivity queries cheap.
- Course: Competitive Programming study plan
- Module: Disjoint set union (DSU)
- Kind: Lesson
- Reading time: 14 min
- Runtime: Clang 18 · C++20
What is a disjoint set union (DSU)?
A disjoint set union (DSU), also called union-find, keeps elements split into groups and answers "are a and b in the same group?" while groups merge. Each group is a tree stored in a parent array; find walks to the root that names the group and unite hangs one root under the other. With union by size and path compression both run in almost constant amortised time.
Lesson
A DSU answers one question fast while groups keep merging: are a and b connected yet? Contest uses: components after each edge, cycle detection, Kruskal's minimum spanning tree, offline "merge these, then ask".
The structure
- Each group is a tree;
p[x]is one step fromxtowards its root, and a root is its own parent. - The root names the group:
aandbare together exactly whenfind(a) == find(b). sz[r]is the number of elements under rootr— read only at a root.
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already together
if (sz[a] < sz[b]) swap(a, b); // a is the larger root
p[b] = a;
sz[a] += sz[b];
return true;
}
};Two rules keep it fast
- Union by size: the smaller root goes under the larger. An element only sinks one level when its group at least doubles, so a tree is never taller than log2 n.
- Path compression:
p[x] = find(p[x])re-points every node it walks straight at the root. - Together: amortised O(α(n)) per call — effectively constant. Either one alone is already O(log n).
unite(0,1), unite(2,3), unite(0,2), unite(4,5), unite(4,6), unite(3,6), find(5)- Seven elements, seven sets: every element is its own root, so parent[i] = i and size[i] = 1. The size row is only read at a root.
- unite(0, 1): Both sets have size 1, a tie, so 0 stays the root and size[0] becomes 2.
- unite(2, 3): Both sets have size 1, a tie, so 2 stays the root and size[2] becomes 2.
- unite(0, 2): Both sets have size 2, a tie, so 0 stays the root and size[0] becomes 4. Now 3 sits two links below its root — the only kind of path compression can shorten.
- unite(4, 5): Both sets have size 1, a tie, so 4 stays the root and size[4] becomes 2.
- unite(4, 6): The set of 6 is smaller, so its root 6 goes under 4 and size[4] becomes 3.
- unite(3, 6) starts with find(3), which walks 3 → 2 → 0 to the root 0.
- Path compression: on the way back every node of that walk points straight at 0, so parent[3] is now 0 and the next find(3) is one step.
- find(6) is 6 → 4. The set of 0 has 4 elements and the set of 4 has 3, so 4 goes under 0: one set of 7.
- A later find(5) walks 5 → 4 → 0 once and flattens it. Union by size keeps every tree at most log2 n tall; path compression flattens what is walked, and together a find costs almost O(1).
Contest habits
unitereturningfalseis the cycle test: the edge joined two vertices that were already connected.- Keep a running
componentscounter: start atn, subtract one on every successfulunite. - The recursive
findis fine at 2 × 10^5 with union by size (depth ≤ 18). Without it, a chain of 10^6 can overflow the stack. - Index from 0 or convert 1-based input once at read time — never mix.
More practice
Common questions
What is path compression in union-find?
During find(x), every node on the walk from x to its root is re-pointed straight at the root, so the next find on any of them takes one step. It is one line in the recursive form: return p[x] == x ? x : p[x] = find(p[x]);.
Why use union by size or by rank?
Hanging the smaller tree under the larger one means an element only gets one link deeper when its group at least doubles, so no tree is ever taller than log2 n. Without it, uniting in a chain order builds a path of length n and every find costs O(n).
What is the time complexity of DSU with both optimisations?
O(α(n)) amortised per operation, where α is the inverse Ackermann function — at most 4 for any input that fits in memory. In practice, treat each find and unite as O(1); a contest with 2 × 10^5 operations runs in milliseconds.
How do you detect a cycle in an undirected graph with DSU?
Add the edges one at a time. Before uniting the endpoints of an edge, call find on both: if they already have the same root, the endpoints were connected before this edge, so the edge closes a cycle.
Exercises
Components after every union
There are n people, numbered 1 to n, each in a group of their own. q times, two people u and v join groups (if they are already in the same group, nothing changes). After every join, print two numbers: how many groups there are, and the size of the largest group.
Input: n q, then q lines u v (1 ≤ n ≤ 2·10^5, 1 ≤ q ≤ 2·10^5, 1 ≤ u, v ≤ n; u = v is allowed). Output: q lines <groups> <largest>.
6 5
1 2
3 4
2 1
2 4
5 6prints
5 2
4 2
4 2
3 4
2 4The first edge that closes a cycle
An undirected graph on vertices 1 to n receives m edges one at a time. Print the 1-based index of the first edge whose two endpoints were already connected before it arrived — the first edge that closes a cycle. A self-loop v v closes a cycle at once. Print -1 when no edge does.
Input: n m, then m lines u v (1 ≤ n ≤ 2·10^5, 0 ≤ m ≤ 2·10^5). Output: one integer.
5 6
1 2
2 3
4 5
3 4
1 3
2 5prints
5Edge 5 (1 3) arrives after 1 2 and 2 3 have already connected 1 and 3.
In this module: Disjoint set union (DSU)
← Checkpoint — Number theory · Checkpoint — Disjoint set union →