Union-find, also called a disjoint-set data structure or DSU, keeps elements in sets that never overlap: find tells which set holds an element, and union merges two sets. With union by rank and path compression, both take almost constant time. This page explains how it works, with step-by-step animations of union by rank and path compression from the VisiGrab app.
// how union-find works
Union-find, also called a disjoint-set data structure, disjoint set union (DSU) or merge-find set, keeps elements in sets that never overlap. It answers two questions in almost constant time: which set holds an element, and whether two elements are in the same set. Find names an element's set, and union merges two sets into one.
Bernard Galler and Michael Fischer described its forest of parent links in 1964, and Robert Tarjan proved its near-constant cost in 1975.
Each set is a tree, and the trees together form a forest. Every node keeps one link, to its parent. The root is the node that is its own parent: the set's representative. Two elements share a set exactly when they share a root. In code, each element number indexes its parent and its rank: for a root, its rank is a bound on its tree's height.
The app draws element 0 as A, 1 as B and so on, leaves out each root's link to itself, and writes the rank above each root.
1. Make-set: each element starts as its own parent with rank 0, a set of one.
2. Find: from the element, follow parent links upwards until a node is its own parent. That root is the answer.
3. Path compression: once the root is known, link every node on the walked path straight to it, so the next find from any of them takes one step.
4. Union: find the roots of both elements. If they are the same, the elements already share a set and the union stops. Otherwise one root becomes the child of the other: the link itself changes only that root's parent, and every node below it keeps its parent.
5. Union by rank: the root of higher rank becomes the parent, and its rank stays. When the ranks are equal, the first element's root becomes the parent and its rank goes up by one. Only a union changes a rank, and only on a tie.
The app's code is a class UnionFind whose constructor makes every element a set of its own. In pseudocode:
UnionFind(count)
for i from 0 to count - 1
parent[i] = i
rank[i] = 0
find(element)
if parent[element] != element
root = find(parent[element])
parent[element] = root
return parent[element]
union(x, y)
xRoot = find(x)
yRoot = find(y)
if xRoot == yRoot
return
if rank[xRoot] < rank[yRoot]
parent[xRoot] = yRoot
else if rank[xRoot] > rank[yRoot]
parent[yRoot] = xRoot
else
parent[yRoot] = xRoot
rank[xRoot] = rank[xRoot] + 1
find calls itself up the path until parent[element] == element, the root. As the calls return, each node on the path gets root as its parent, the node nearest the root first; a node whose parent is already the root stays as it is. union finds both roots, which compresses both paths, and returns if they match. On a tie the last branch keeps xRoot, the first element's root, on top; the textbook Introduction to Algorithms (CLRS) breaks the tie the other way, and both are correct.
The first player merges the sets of A and C, two trees of rank 1: A over B, and C over D. The ranks tie, so A becomes the parent and its rank rises to 2. Only C gets a new parent: D stays under C, and C's rank is no longer shown, as only a root's rank counts.
The second player starts from that tree, A of rank 2, beside F's tree of rank 1, F over G. F goes under A, and A keeps rank 2. G ends two levels below A, as deep as D, so the tree grows no taller.
A root reaches rank k only when two trees of rank k − 1 merge, so its tree holds at least 2k nodes. With n elements no rank exceeds log2 n, so no find walks more than log2 n links.
Union by size, also called weighted quick-union, stores each root's node count instead and hangs the smaller tree under the larger. It gives the same height bound and the same cost with path compression. Choose it when a problem needs the size of each set; otherwise either works.
Instead of Union A and F, three other unions on the second player's starting forest, with J and K as two extra single-node sets, give A a tree of rank 3: H and I, F and H, then D and F; the last one's find has already linked D straight to A. Find I links H and I straight to A, while F, already under A, stays where it is. The tree's height drops from 3 to 2, but A's rank stays 3.
Path splitting and path halving are one-pass variants without recursion: they link each node on the path, or every other node, to its grandparent. Both keep the same bound.
Both keep the trees flat, so a find walks few parent links. Union by rank puts the root of lower rank under the other, so a rank rises only when two trees of equal rank merge, and no rank exceeds log2 n. Path compression links every node a find walks straight to the root; together they bring each operation down to O(α(n)) amortized, almost constant.
Path compression never updates a rank, since finding the new height would mean measuring the root's other subtrees. A rank is therefore an upper bound on the height: a tree can be shorter than its rank, never taller, and the near-constant cost needs only that bound. That is why union by rank, not union by height, goes with path compression.
With n elements:
| Technique | One find, worst case | Amortized per operation |
|---|---|---|
| Neither | O(n) | O(n) |
| Union by rank | O(log n) | O(log n) |
| Path compression | O(n) | O(log n) |
| Both | O(log n) | O(α(n)) |
α(n) is the inverse Ackermann function. The Ackermann function grows so fast that its inverse is at most 4 for any number of elements a computer could hold. The bound is amortized: one find can still walk a long path, but it flattens that path for the finds that follow. A union whose roots are known changes one link, in O(1). Space is O(n): one parent and one rank per element.
On a graph known in full, a depth-first or breadth-first search from each unvisited vertex labels every connected component in O(V + E). Union-find suits edges that arrive over time: each new edge is one union, and asking whether two vertices are connected takes two finds. It gives no path between them, ignores edge directions, and cannot split a set or delete an edge.
The app's listing follows the pseudocode above in all three languages, with a link to the full source on GitHub. Its recursive find is safe: by the rank bound, a million elements nest at most about 20 calls.
Note
In C++, union is a reserved keyword, so the app's C++ listing names the method union_sets.
The full source code is on GitHub, in Python, Java and C++.
// in the app
In VisiGrab, union-find runs nine prepared unions and finds on lettered trees with a message for every step, and lets you merge sets of your own.
Buttons in the info dialog's Union and Find tabs start nine operations, the three on this page among them. In Union D and F, Union I and E and Union H and E, a find compresses a path before the two roots merge.
The topic opens on nine single-node sets, A to I: tap two nodes in different sets and merge them step by step, until the app says all nodes are one set. An Operations log numbers every union and find so far.
Info, Union, Find and Efficiency: the forest and its roots, both rank rules with pictures, path compression and the fact that it leaves ranks alone, and the amortized cost with the inverse Ackermann function.
One UnionFind class per language, with a recursive find that compresses the path and a union by rank, named union_sets in C++. Three numbered notes cover initialization, path compression and union by rank, and a link leads to the full source on GitHub.
Ten questions, every option explained: what the sets are, how a root is recognized, what a merge changes, both rank rules, what a rank means, path compression and what it costs.
The Kruskal topic draws a union-find of the graph's vertices together with the graph: each edge is checked by the sets of its ends, and every edge taken merges two roots.
// build your own
Download VisiGrab to run nine unions and finds step by step, then merge the nine sets A to I yourself and watch the ranks grow.
Union-find is one of 30+ topics. See them all