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
Successive analyses narrowed the cost of combining weighted union with path compression, or the collapsing rule. Hopcroft and Ullman gave an upper bound in 1973; Tarjan proved a tight maximum cost of in 1975. These sequences start with singleton sets and intermix FIND operations with UNION operations, so counts FINDs. In 1989, Fredman and Saks proved a total lower bound of cell accesses for hard sequences in the online cell-probe model with bits per cell.23
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 total-cost upper bound for initialization of elements followed by union/find operations. Here is a standard one-variable inverse Ackermann function:
Executable example
C++20
The C++20 version stores element indices in size_t. Method arguments must be within the count elements created by the constructor. Since union is a C++ keyword, the merge method is named unite; a size tie keeps the first argument’s root, just as in TypeScript.
#include <cstddef>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class UnionFind {
std::vector<std::size_t> parent;
std::vector<std::size_t> sizes;
public:
explicit UnionFind(std::size_t count) : parent(count), sizes(count, 1) {
std::iota(parent.begin(), parent.end(), std::size_t{0});
}
std::size_t find(std::size_t value) {
auto root = value;
while (root != parent[root]) root = parent[root];
while (value != root) {
const auto next = parent[value];
// Point each node on the traversed path directly at the root.
parent[value] = root;
value = next;
}
return root;
}
bool unite(std::size_t a, std::size_t b) {
auto rootA = find(a);
auto rootB = find(b);
if (rootA == rootB) return false;
if (sizes[rootA] < sizes[rootB]) std::swap(rootA, rootB);
parent[rootB] = rootA;
sizes[rootA] += sizes[rootB];
return true;
}
std::size_t sizeOf(std::size_t value) {
return sizes[find(value)];
}
};
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;
}true
false
false
4TypeScript
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));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.
Cost and practical boundaries
Initializing elements takes time and space. The inverse Ackermann function grows so slowly that amortized operation costs remain small at realistic input sizes. The time bound above includes initialization and the accumulated cost of the operation sequence.
Basic union–find stores the connectivity partition, not every original graph edge or alternate route. Even without path compression, its tree alone cannot generally determine connectivity after an edge deletion. Offline queries and backtracking that undo recent unions usually omit path compression and use linking by size, giving worst-case finds. An undo stack restores the previous parent and size values changed by a union. A rollback implementation with path compression must also log every parent rewrite caused by compression and analyze those costs. Linking by size with compression suits incremental connectivity and cycle detection in Kruskal’s minimum spanning tree algorithm.
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. ↩
- John E. Hopcroft, Jeffrey D. Ullman, “Set Merging Algorithms,” SIAM Journal on Computing 2(4), 1973, pp.294–303. DOI. Tarjan 1975 defines t(m,n) as maximum sequence time; Fredman–Saks 1989, Theorem 5, states the CPROBE(log n) lower bound. ↩