I think of Union-Find, also called the Disjoint Set Union (DSU) data structure, as one of the most elegant tools I have for tracking connectivity between elements as relationships are added over time. It lets me efficiently answer two kinds of questions: are two elements part of the same group, and how do I merge two groups together. Despite its conceptual simplicity, I find its performance characteristics genuinely surprising, since with the right optimizations, it becomes almost, but not quite, constant time per operation.
History and Background
I trace the roots of Union-Find back to work in the 1960s, with early analysis appearing in a 1964 paper by Bernard Galler and Michael Fischer. The structure was refined over the following decades, with key contributions from Robert Tarjan, who in 1975 provided a tight analysis of the data structure’s performance when combined with two specific optimizations, path compression and union by rank, showing that a sequence of operations runs in time related to the inverse Ackermann function, an astonishingly slow-growing function. This analysis became a landmark result in the study of amortized algorithm complexity, and Union-Find has since become a standard tool taught in essentially every algorithms course, largely because of Tarjan’s work establishing just how efficient it really is.
Problem Statement
Union-Find solves the dynamic connectivity problem: given a collection of elements that start out in their own separate groups, I need to efficiently support two operations as they are interleaved over time: merging (union) two groups into one, and checking (find) whether two elements currently belong to the same group. This comes up whenever I am tracking connected components in a graph that is being built incrementally, such as determining whether two computers are on the same network as connections are added, or whether two land plots are part of the same contiguous region as adjacent plots are merged.
Core Concepts
Terms I use throughout my explanation:
- Disjoint sets: a collection of sets where no element belongs to more than one set at the same time.
- Representative (or root): a designated element that identifies which set a group belongs to; two elements are in the same set if and only if they share the same representative.
- Find operation: given an element, determines which set it belongs to by returning its representative.
- Union operation: merges the sets containing two given elements into a single set.
- Path compression: an optimization where, during a find operation, I make every node on the path point directly to the root, flattening the tree structure for faster future lookups.
- Union by rank (or size): an optimization where, during a union operation, I attach the smaller or shallower tree under the root of the larger or deeper tree, keeping the overall structure balanced.
How It Works
I break Union-Find into its two core operations plus initialization.
- Initialization (MakeSet): I create $n$ separate sets, one for each element, where each element initially points to itself as its own representative.
- Find: given an element, I follow its parent pointers upward until I reach an element that points to itself, which is the representative of that set. With path compression, I then update every node visited along this path to point directly to the representative, so future find operations on those nodes are faster.
- Union: given two elements, I first find the representative of each. If they are already the same, I do nothing, since the elements are already in the same set. Otherwise, I merge the two sets by making one representative point to the other. With union by rank (or size), I attach the tree with the smaller rank (or fewer elements) under the root of the tree with the larger rank, to keep the overall tree shallow.
Working Principle
I find that the real power of Union-Find comes from combining its two optimizations. Without any optimization, a naive implementation can degrade into a long chain (essentially a linked list) if unions are always performed in an unlucky order, making find operations take $O(n)$ time in the worst case. Union by rank prevents this by always attaching the shorter tree beneath the taller one, which mathematically guarantees the tree’s height grows only logarithmically with the number of elements. Path compression takes this further: every time I perform a find, I flatten the path traversed so that those nodes will connect directly to the root next time, meaning the structure keeps getting flatter with use. When both optimizations are used together, the amortized time per operation becomes nearly constant, formally bounded by the inverse Ackermann function, which for any practically imaginable input size is less than 5, meaning the algorithm behaves as if it were constant time for all practical purposes.
Mathematical Foundation
With only union by rank, the height of any tree is bounded by:
$$\text{height} \leq \log_2(n)$$
where $n$ is the number of elements in the set, giving $O(\log n)$ time per find operation.
With both path compression and union by rank combined, Tarjan showed that a sequence of $m$ operations on $n$ elements takes:
$$O(m \cdot \alpha(n))$$
total time, where $\alpha(n)$ is the inverse Ackermann function, defined as the smallest $k$ such that $A(k, k) \geq n$, with $A$ being the extremely fast-growing Ackermann function. Because $\alpha(n)$ grows so slowly, it is less than 5 for any value of $n$ that could conceivably be represented in the physical universe, so I treat this bound as effectively $O(1)$ amortized time per operation in practice.
Diagrams
flowchart TD
A["MakeSet: each element is its own root"] --> B["Union(x, y): find roots of x and y"]
B --> C{"Are roots the same?"}
C -->|Yes| D["Already in same set, do nothing"]
C -->|No| E["Attach smaller-rank root under larger-rank root"]Pseudocode
function MAKE_SET(n):
parent = array of size n
rank = array of size n, initialized to 0
for i in 0 to n - 1:
parent[i] = i
return parent, rank
function FIND(parent, x):
if parent[x] != x:
parent[x] = FIND(parent, parent[x]) // path compression
return parent[x]
function UNION(parent, rank, x, y):
root_x = FIND(parent, x)
root_y = FIND(parent, y)
if root_x == root_y:
return // already in the same set
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
else if rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] = rank[root_x] + 1
Step-by-Step Example
I will trace through a sequence of operations on 6 elements, labeled 0 through 5.
- I call
MAKE_SET(6), so each element starts as its own set:parent = [0, 1, 2, 3, 4, 5]. - I call
UNION(0, 1). Both are their own roots with equal rank, so I attach1under0and increase0‘s rank:parent = [0, 0, 2, 3, 4, 5]. - I call
UNION(2, 3). Similarly, I attach3under2:parent = [0, 0, 2, 2, 4, 5]. - I call
UNION(0, 2). Both roots (0and2) have equal rank (both rank 1), so I attach2under0and increase0‘s rank to 2:parent = [0, 0, 0, 2, 4, 5]. - I call
FIND(3). I follow3 -> 2 -> 0, reaching root0. With path compression, I updateparent[3] = 0directly andparent[2]was already0. - I call
UNION(4, 5), attaching5under4:parent = [0, 0, 0, 0, 4, 5](position 3 now points directly to 0 due to path compression from step 5). - I call
FIND(1)andFIND(5)to check if elements 1 and 5 are connected:FIND(1)returns0,FIND(5)returns4, so they are not in the same set, since0 != 4.
Time Complexity
With both path compression and union by rank applied, a sequence of $m$ Find and Union operations on $n$ elements takes $O(m \cdot \alpha(n))$ total time, where $\alpha(n)$ is the inverse Ackermann function, which I treat as effectively constant for any realistic input size. Without these optimizations, a naive implementation can degrade to $O(n)$ time per find operation in the worst case, since the underlying tree can become a long chain. Using only one of the two optimizations still gives a solid $O(\log n)$ time per operation, since either optimization alone is enough to bound tree height logarithmically.
Space Complexity
Union-Find requires $O(n)$ space to store the parent array (and the rank or size array used for the union-by-rank optimization) for $n$ elements. This space usage stays constant regardless of how many union or find operations are performed, since the data structure never grows beyond its initial number of elements, only its internal tree shape changes.
Correctness Analysis
I reason about correctness by observing that the data structure maintains an invariant: at all times, two elements belong to the same set if and only if following their parent pointers eventually leads to the same root. The MAKE_SET initialization trivially satisfies this, since every element starts as its own root and thus its own singleton set. Each UNION operation preserves the invariant by connecting the root of one set to the root of another, merging exactly those two sets and leaving all other sets untouched, since only the two roots’ parent pointers change. Path compression does not break this invariant either, since it only shortens the path from a node to its existing root, it never changes which root a node ultimately belongs to. Because both operations preserve the fundamental invariant, the structure always correctly reflects the true grouping of elements based on the unions performed so far.
Advantages
- I find the near-constant amortized time per operation, thanks to path compression and union by rank, exceptionally fast in practice, even for very large numbers of elements and operations.
- The implementation is simple, requiring just two small arrays and a handful of lines of logic.
- It handles dynamic connectivity naturally, letting me add new connections (unions) at any time without needing to rebuild the whole structure.
- It uses very little memory, just $O(n)$ space, with a small constant factor.
Disadvantages
- Union-Find does not support removing a connection once it has been made (deleting a union), since the structure is designed around merging sets, not splitting them apart; if I need to undo unions, I need a different, more complex structure.
- It only tells me whether two elements are connected, not the actual path or specific edges connecting them, so if I need path information (like the shortest path between two nodes), I need to combine it with other graph algorithms.
- The near-constant time guarantee only holds with both optimizations properly implemented; a naive version without path compression or union by rank can be significantly slower in adversarial cases.
Applications
I reach for Union-Find in several common scenarios: detecting cycles in an undirected graph while building a minimum spanning tree using Kruskal’s algorithm, where I check whether two vertices are already connected before adding an edge that would create a cycle; tracking connected components in image processing tasks, such as identifying connected regions of pixels; implementing “friend circles” or social network group detection; and solving grid-based connectivity puzzles, such as determining whether a path exists from the top to the bottom of a randomly generated maze or percolation grid.
Implementation in C
#include <stdio.h>
#define MAX_N 100
int parent[MAX_N];
int rank_arr[MAX_N];
void make_set(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank_arr[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); /* path compression */
}
return parent[x];
}
void union_sets(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if (root_x == root_y) {
return; /* already in the same set */
}
if (rank_arr[root_x] < rank_arr[root_y]) {
parent[root_x] = root_y;
} else if (rank_arr[root_x] > rank_arr[root_y]) {
parent[root_y] = root_x;
} else {
parent[root_y] = root_x;
rank_arr[root_x]++;
}
}
int main() {
int n = 6;
make_set(n);
union_sets(0, 1);
union_sets(2, 3);
union_sets(0, 2);
union_sets(4, 5);
printf("Find(3) = %d\n", find(3));
printf("Find(1) = %d\n", find(1));
printf("Find(5) = %d\n", find(5));
printf("Are 1 and 3 connected? %s\n", (find(1) == find(3)) ? "Yes" : "No");
printf("Are 1 and 5 connected? %s\n", (find(1) == find(5)) ? "Yes" : "No");
return 0;
}
Sample Input and Output
Running the program with 6 elements and the union operations (0,1), (2,3), (0,2), and (4,5) produces Find(3) = 0, Find(1) = 0, and Find(5) = 4, matching the manual trace from the step-by-step example. The program then reports that elements 1 and 3 are connected (Yes, since both resolve to root 0), while elements 1 and 5 are not connected (No, since they resolve to different roots, 0 and 4 respectively), correctly reflecting the two separate groups formed by the union operations performed.
Optimization Techniques
I rely on these two optimizations as standard practice, and I would rarely implement Union-Find without them:
- Path compression: flattening the tree during every find operation so that future lookups on the same nodes become faster, which I showed in the pseudocode and C implementation above.
- Union by rank or union by size: always attaching the smaller or shallower tree beneath the larger one during a union, preventing the structure from becoming unbalanced.
- Using path splitting or path halving as alternatives to full path compression, which achieve similar asymptotic performance with slightly simpler, non-recursive implementations, useful in environments where recursion depth or call overhead is a concern.
- Preallocating the parent and rank arrays to the maximum expected size upfront, avoiding dynamic resizing overhead during a long sequence of operations.
Common Mistakes
I often see the mistake of implementing Union-Find without either optimization, which still produces correct results but can degrade to $O(n)$ time per operation in bad cases, defeating the whole purpose of using the structure. Another mistake is applying union by rank incorrectly, such as comparing tree sizes instead of ranks without adjusting the tie-breaking logic accordingly, which does not break correctness but can reduce the performance benefits. I also see confusion between the “representative” element and the “value” I actually care about, forgetting that Union-Find only tracks grouping relationships, not any auxiliary data about each group, unless I add extra bookkeeping myself to track things like group size or aggregate properties alongside the core structure.
Further Reading
- Tarjan, R. E. “Efficiency of a Good But Not Linear Set Union Algorithm.” Journal of the ACM, 1975. https://dl.acm.org/doi/10.1145/321879.321884
- Galler, B. A., and Fischer, M. J. “An Improved Equivalence Algorithm.” Communications of the ACM, 1964. https://dl.acm.org/doi/10.1145/364099.364331
- Cormen, T., Leiserson, C., Rivest, R., and Stein, C. “Introduction to Algorithms,” chapter on Data Structures for Disjoint Sets. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Sedgewick, R., and Wayne, K. “Algorithms,” section on Union-Find. https://algs4.cs.princeton.edu/15uf/
