Disjoint Set Union
Union-find for dynamic connectivity and component bookkeeping when edges only merge components.
Disjoint Set Union
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Disjoint Set Union is the data structure for connectivity under merges. It keeps track of which elements belong to the same component while supporting fast ``find the leader'' and ``merge the two components'' operations.
In competitive programming, DSU shows up everywhere: Kruskal, offline connectivity, component counting on grids, small-to-large style reasoning, and rollback-based dynamic connectivity.
When to Use It
Use it when:
components only merge and never split,
queries ask whether two elements are in the same component,
you want to maintain a simple statistic per component such as size,
the graph evolves by adding edges rather than deleting them.
If the problem needs deletions or cut operations, plain DSU is usually the wrong tool and rollback DSU or a dynamic tree structure becomes more relevant.
Core Idea
Represent each component as a rooted tree. Every node points to a parent, and the root of each tree is the component leader.
The two operations are:
find(x): climb to the root and return the leader,
unite(a, b): connect the roots if they are different.
The tree itself is not the graph component. It is only an internal representation of the partition.
Key Insight
The reason DSU is fast is the combination of two heuristics:
path compression: after finding the root, rewrite the visited path so future finds are shorter,
union by size or rank: attach the smaller tree under the larger one.
Path compression makes repeated finds on the same region cheaper. Union by size keeps the internal trees from growing deep in the first place. Together they make the amortized cost essentially constant for contest purposes.
Operations / Main Technique
The standard interface is:
find(x),
unite(a, b),
same(a, b),
size(x).
Component invariant.
Only the root stores component-wide information such as size. That is a useful mental rule: if a value should mean ``for the whole set'', keep it on the leader.
Worked example.
If \(\{1, 2, 3\}\) and \(\{4, 5\}\) are separate components, uniting \(2\) and \(5\) does not attach those exact vertices conceptually. It finds their leaders first, then merges the two whole components through those leaders.
Correctness Intuition
At all times, every element belongs to exactly one leader tree. Two elements are in the same component exactly when their leaders are equal.
Path compression does not change the partition, because it only shortcuts parent pointers inside one component toward the same root. Union by size also preserves correctness, because it merges two different roots into one new component without losing any membership relation.
Complexity Analysis
With path compression and union by size/rank:
find,unite,same,size: \(O(\alpha(n))\) amortized,memory: \(O(n)\).
The inverse Ackermann function \(\alpha(n)\) grows so slowly that for contest input sizes it behaves like a tiny constant.
Implementation
The reference code stores one array parent where roots keep negative component sizes and non-roots keep their parent index. That layout is compact and keeps all the basic operations together.
It also tracks the number of connected components explicitly, which is often convenient in graph problems where the final answer depends on how many merges succeeded.
Common Pitfalls
Forgetting to find the leaders before merging.
Mixing ``rank'' and ``size'' logic halfway through one implementation.
Updating component data on a non-root instead of the root.
Assuming DSU can handle deletions just because connectivity is involved.
Adding path compression to a rollback DSU, where that optimization becomes inconvenient or incorrect.
Variants / Extensions
DSU rollback for offline dynamic connectivity,
DSU with parity or xor distance information,
DSU that stores custom data per component,
offline painting / next-unprocessed-cell DSU tricks,
union-by-size ``small to large'' ideas on explicit containers.
Rollback DSU is the extension I see most often in harder contest problems, especially when edges are added and removed over time but the whole query sequence is known offline.
Practice Problems
Kruskal minimum spanning tree.
Grid component counting after activating cells.
Offline connectivity where edges are processed in reverse time.
Problems that require storing one extra statistic such as component sum or bipartite validity.
References
Code
Contest-ready reference implementation for the idea explained above.
struct DSU {
vector<int> parent; // root stores -size, non-root stores parent
int components = 0;
DSU() = default;
explicit DSU(int n) { init(n); }
void init(int n) {
parent.assign(n, -1);
components = n;
}
int find(int x) {
if (parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
int leader(int x) {
return find(x);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (-parent[a] < -parent[b]) swap(a, b);
parent[a] += parent[b];
parent[b] = a;
--components;
return true;
}
bool same(int a, int b) {
return find(a) == find(b);
}
int size(int x) {
return -parent[find(x)];
}
int component_count() const {
return components;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.