Part 1 · Concepts · Graphs
Union-find (disjoint set)
Tracks which items are in the same group, with near O(1) merge and same-group checks.
How it works
Every item points to a parent, and the root names the group. find walks up to the root and flattens the path as it goes (path compression). union links one root under the other, attaching the shorter tree under the taller (union by rank). Together these make operations effectively constant time.
| find / union | about O(1) amortized (inverse Ackermann) |
| space | O(n) |
Reach for it when
- Group or merge sets as edges arrive
- Detect a cycle in an undirected graph
- Count connected components dynamically
- Kruskal's minimum spanning tree
Implementation (JavaScript, tested)
class UnionFind {
parent;
rank;
count; // number of separate groups
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
this.count = n;
}
find(x) {
while (this.parent[x] !== x) {
this.parent[x] = this.parent[this.parent[x]]; // path halving: flatten as we climb
x = this.parent[x];
}
return x;
}
union(a, b) {
let ra = this.find(a),
rb = this.find(b);
if (ra === rb) return false; // already together (in a graph: a cycle)
if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra; // hang the shorter tree under the taller
if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
this.count--;
return true;
}
}Traps
- Without path compression and rank it can be O(n) per find.
- It can merge groups but not split them.
In real systems: Merging duplicate customer records or accounts that share a phone or email, clustering, image region labeling.
Say out loud: If I only need 'are these connected' while merging groups, union-find is simpler than running BFS each time.