Union-find
Overview
Union–find (or a disjoint-set data structure) maintains a collection of non-overlapping sets, supporting two primary operations: merging two sets (union) and testing whether two elements belong to the same set (find). Rather than relabeling every member whenever two groups merge, each group elects a root representative and merges link one root to the other.
History
Bernard A. Galler and Michael J. Fischer introduced parent-pointer trees for equivalence classes in their 1964 paper “An Improved Equivalence Algorithm” to process FORTRAN EQUIVALENCE statements.1
Determining the exact asymptotic cost of combining weighted union (linking the smaller tree under the larger) with path compression (the collapsing rule) took another decade. John E. Hopcroft and Jeffrey D. Ullman proved an iterated-logarithm bound of in 1973; in 1975, Robert E. Tarjan proved the tight bound governed by the inverse Ackermann function . In 1989, Michael L. Fredman and Michael E. Saks showed in the cell-probe model that any disjoint-set representation requires amortized time per operation.2
Union by size and path compression
Every element stores a parent index , while a root representative points to itself (). Calling find(x) follows parent pointers to the root; two elements belong to the same set if and only if they share a root. Because a merge can change which root represents a set, domain-level group metadata should be keyed by the current root or stored externally rather than assuming a fixed representative ID.
Naively attaching one root to another can degenerate into a chain of height . Linking the smaller tree under the larger tree’s root (union by size) ensures that whenever an element’s depth increases by , the size of its containing set at least doubles, bounding tree height by even without path compression. Adding path compression—rewiring every node visited during find(x) directly to the root—yields the following invariants and amortized bound for operations on elements:
Executable example
Start with five singleton sets 0..4, merge {0, 1} and {2, 3}, and then join those two pairs while leaving 4 separate. Calling union on elements that already share a root returns false so callers can tell whether the number of connected components decreased.
class UnionFind {
private parent: number[];
private sizes: number[];
constructor(count: number) {
this.parent = Array.from({ length: count }, (_, index) => index);
this.sizes = new Array<number>(count).fill(1);
}
find(value: number): number {
let root = value;
while (root !== this.parent[root]) root = this.parent[root]!;
while (value !== root) {
const next = this.parent[value]!;
// Point every traversed node directly at the root (path compression).
this.parent[value] = root;
value = next;
}
return root;
}
union(a: number, b: number): boolean {
let rootA = this.find(a);
let rootB = this.find(b);
if (rootA === rootB) return false;
// Attach the smaller tree under the larger tree’s root to bound height.
if (this.sizes[rootA]! < this.sizes[rootB]!) [rootA, rootB] = [rootB, rootA];
this.parent[rootB] = rootA;
this.sizes[rootA] = this.sizes[rootA]! + this.sizes[rootB]!;
return true;
}
sizeOf(value: number): number {
return this.sizes[this.find(value)]!;
}
}
const groups = new UnionFind(5);
groups.union(0, 1);
groups.union(2, 3);
groups.union(1, 2);
console.log(groups.find(0) === groups.find(3));
console.log(groups.find(0) === groups.find(4));
console.log(groups.union(0, 3));
console.log(groups.sizeOf(3));Output:
true
false
false
4Elements 0 and 3 now share a root while 4 remains distinct. Merging 0 and 3 a second time is a no-op, leaving sizeOf(3) at 4. Because only a root’s sizes entry reflects the current set cardinality, sizeOf always resolves this.find(value) first.
C++ example
Because union is a reserved keyword in C++, the merge method is named unite, and std::iota initializes the parent array to .
#include <cstddef>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class UnionFind {
public:
explicit UnionFind(std::size_t count) : parent_(count), sizes_(count, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int value) {
int root = value;
while (root != parent_[root]) root = parent_[root];
while (value != root) {
int next = parent_[value];
// Point every traversed node directly at the root (path compression).
parent_[value] = root;
value = next;
}
return root;
}
bool unite(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return false;
// Attach the smaller tree under the larger tree’s root to bound height.
if (sizes_[rootA] < sizes_[rootB]) std::swap(rootA, rootB);
parent_[rootB] = rootA;
sizes_[rootA] += sizes_[rootB];
return true;
}
std::size_t sizeOf(int value) { return sizes_[find(value)]; }
private:
std::vector<int> parent_;
std::vector<std::size_t> sizes_;
};
int main() {
UnionFind groups(5);
groups.unite(0, 1);
groups.unite(2, 3);
groups.unite(1, 2);
std::cout << std::boolalpha;
std::cout << (groups.find(0) == groups.find(3)) << '\n';
std::cout << (groups.find(0) == groups.find(4)) << '\n';
std::cout << groups.unite(0, 3) << '\n';
std::cout << groups.sizeOf(3) << '\n';
return 0;
}Output:
true
false
false
4Cost and practical boundaries
Initializing elements takes time and space. Because the inverse Ackermann function satisfies for all , union–find operates in effectively constant amortized time per operation.
One key boundary is that union–find is an incremental (addition-only) structure: it cannot efficiently split sets or delete edges once path compression has flattened ancestor chains. When backtracking or offline dynamic connectivity requires undoing recent unions (rollback), omit path compression, rely on union by size alone ( worst-case time per query), and record parent/size writes on an undo stack. For incremental connectivity and cycle detection in Kruskal’s minimum spanning tree algorithm, union by size with path compression is the standard choice.
See also
Footnotes
- Bernard A. Galler, Michael J. Fischer, “An Improved Equivalence Algorithm,” Communications of the ACM 7(5), 1964, pp.301–303, DOI. For the lineage and weighted union/collapsing analysis: Robert E. Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, ERL-M434, 1974-03-28, introduction and pp.2–4, institutional copy; JACM 22(2), 1975, pp.215–225, DOI. ↩
- Michael L. Fredman, Michael E. Saks, “The Cell Probe Complexity of Dynamic Data Structures,” Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), 1989, pp.345–354, DOI. ↩