Union-Find (Disjoint Set) Explained: Efficient Set Merging and Cycle Detection
Some problems boil down to a single repeated question: are these two things connected, directly or through a chain of other connections? Union-Find answers that question, and lets you merge groups together, in time so close to constant that it is treated as constant in practice.
Published July 6, 2026The Problem: Tracking Groups That Merge Over Time
Picture a set of network hosts where you keep learning that pairs of them are on the same subnet. After enough of these facts arrive, you want to answer "are host A and host B on the same subnet?" quickly, even though the grouping keeps changing as new facts come in. A naive approach — keeping an explicit list per group and scanning it — gets slow as groups grow, and merging two large groups means relabeling every element in one of them.
Union-Find (also called Disjoint Set Union, or DSU) represents each set as a tree instead of a list. Every element has a parent pointer; the element whose parent points to itself is the tree's root, and the root doubles as the identifier for the whole set. Two elements are in the same set exactly when following parent pointers from each of them reaches the same root.
The Two Core Operations
- find(x): Follow parent pointers from x until reaching the root, and return that root. Two elements are in the same set if find returns the same root for both.
- union(x, y): Find the roots of x and y. If they differ, make one root point to the other, merging the two trees (and therefore the two sets) into one.
Implemented naively, a long chain of unions can produce a tall, skinny tree where find degenerates to an O(n) linked-list walk. Two optimizations, almost always used together, fix this.
Union by Rank (or Size)
When merging two trees, always attach the root of the smaller tree under the root of the larger one, rather than picking arbitrarily. This keeps the resulting tree's height bounded by roughly log(n), because a tree's height can only increase when it is merged with a tree of at least equal size, and that can happen at most log(n) times before the tree contains all n elements.
Path Compression
While performing find(x), after locating the root, go back and repoint every node visited along the way directly to that root. The next find on any of those nodes then takes a single step. Path compression alone dramatically flattens the tree over repeated finds, and combined with union by rank it gives an amortized time per operation of O(α(n)), where α is the inverse Ackermann function — a function that grows so slowly it is under 5 for any n you could ever construct, so the combined structure is effectively constant time for practical purposes. This bound comes from Robert Tarjan's 1975 analysis of the structure.
Where Union-Find Is Used
| Application | How Union-Find Helps |
|---|---|
| Kruskal's minimum spanning tree algorithm | Processes edges by weight and uses find to reject any edge whose endpoints are already in the same set, which would create a cycle |
| Connected components in a graph | Union every edge's endpoints; the number of distinct roots at the end equals the number of connected components |
| Image processing (connected-component labeling) | Merges adjacent pixels of the same value into regions in a single pass plus a resolution pass |
| Percolation and network reliability models | Tracks whether a path exists from one side of a grid or network to the other as connections are added one at a time |
Conclusion
Union-Find earns its place in the standard algorithms toolkit by being deceptively simple to implement — two arrays and two short functions — while resting on a genuinely subtle complexity analysis. The two optimizations, union by rank and path compression, are individually easy to justify and together produce a bound so close to constant that most people just call it constant and move on. Any time a problem reduces to "keep track of which things are connected as connections are added," Union-Find is worth reaching for before something heavier.
Tarjan's original paper, "Efficiency of a Good But Not Linear Set Union Algorithm", is the source for the inverse-Ackermann bound if you want to see the proof rather than take the result on faith.