Union-Find (Disjoint Set)
Track which elements belong to the same group with near-O(1) union and find.
How it works
Union-Find (also called Disjoint Set Union) is a data structure that tracks a partition of elements into disjoint sets, supporting two core operations: find (which set does element x belong to?) and union (merge the sets containing x and y). Naively, these operations can be O(n), but two optimizations bring the amortized cost to O(α(n)) — effectively constant.
Path compression flattens the tree during a find operation by making every node on the path from x to the root point directly to the root, drastically reducing future traversal depth. Union by rank always attaches the shorter tree under the taller one, bounding the tree height at O(log n) before compression even kicks in.
Together, the two optimizations yield an inverse-Ackermann time complexity α(n) — a function that is at most 4 for any input that could ever exist in practice.
Complexity
Visualizer
Where it's used in the real world
Kruskal's MST algorithm
Cycle detection during edge relaxationKruskal's algorithm adds edges in order of weight and skips any edge whose endpoints are already in the same component. Union-Find answers this in O(α(n)) per edge, making the overall MST algorithm O(E log E).
Network connectivity analysis
Online queries: are nodes A and B reachable from each other?As new network links are established, union-find merges the connected components. Each connectivity query is answered in near-constant time by comparing the roots of the two queried nodes.
Image segmentation (computer vision)
Grouping adjacent pixels with similar color/intensityConnected-component labeling in images iterates over pixel adjacency and unions neighboring pixels that meet a similarity threshold. Union-Find processes millions of pixels efficiently in a single pass.
Implementation
class UnionFind {
private parent: number[];
private rank: number[];
public components: number;
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
this.components = n;
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
union(a: number, b: number): boolean {
const ra = this.find(a);
const rb = this.find(b);
if (ra === rb) return false; // already same set
// union by rank
if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
else { this.parent[rb] = ra; this.rank[ra]++; }
this.components--;
return true;
}
connected(a: number, b: number): boolean {
return this.find(a) === this.find(b);
}
}