Overview
Union-Find, also called Disjoint Set Union (DSU), is a data structure that tracks a collection of elements partitioned into non-overlapping sets. It answers two questions fast: which set does an element belong to, and are two elements in the same set?
Each set is a tree whose root is its representative. Two optimizations — union by rank and path compression — flatten these trees so aggressively that every operation runs in near-constant amortized time.
How Union-Find (DSU) works
- Start with every element in its own singleton set, pointing to itself as parent.
- find(x) follows parent pointers up to the root; path compression re-points every visited node directly at the root.
- union(a, b) finds both roots and, by union by rank, attaches the shorter tree under the taller one.
- Two elements are connected exactly when find returns the same representative.
When to use it
- Kruskal's algorithm for the Minimum Spanning Tree, to detect whether an edge would form a cycle.
- Dynamic connectivity queries in graphs and networks as edges are added.
- Cycle detection in undirected graphs and grouping problems such as image segmentation.
Complexity analysis
With both union by rank and path compression, a sequence of operations runs in O(α(n)) amortized time each, where α is the inverse Ackermann function — effectively a small constant for any practical n. Space is O(n) for the parent and rank arrays.
Frequently asked questions
What is the inverse Ackermann function α(n)?
It grows so slowly that α(n) is at most 4 for any input size that could ever be stored, so each Union-Find operation is treated as effectively constant time.
Why use both union by rank and path compression?
Each alone gives O(log n); combining them keeps trees flat and drops the amortized cost to O(α(n)). Union by rank limits tree height, and path compression shortcuts future lookups.