Lesson 26
Union-Find (Disjoint Sets)
Merge groups and ask 'same group?' in nearly constant time.
01Why it matters & the intuition
Union-find answers connectivity questions as edges stream in — Kruskal's minimum spanning tree, network connectivity, image segmentation and detecting redundant connections all use it.
Think of it like…
Every club has a president. To check if two people are in the same club, ask each who their president is. Merging two clubs just means one president reports to the other. Path compression is everyone remembering the top president directly after asking once.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- find path
- new root
- already joined
03Key ideas
Parent array
parent[i] points toward the set's representative (root). Initially everyone is their own root.
find with path compression
Follow parents to the root, then point every visited node straight at the root so future finds are instant.
union by rank/size
Attach the smaller tree under the larger root so trees stay shallow.
Inverse Ackermann
With both tricks each operation is O(α(n)) — under 5 for any n that fits in the universe. Effectively constant.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class UnionFind {
parent: number[];
size: number[];
components: number;
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.size = new Array(n).fill(1);
this.components = n;
}
find(x: number): number {
while (this.parent[x] !== x) {
this.parent[x] = this.parent[this.parent[x]]; // path halving
x = this.parent[x];
}
return x;
}
union(a: number, b: number): boolean {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return false;
if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra;
this.size[ra] += this.size[rb];
this.components--;
return true;
}
}05Complexity
| Operation | Time | Space |
|---|---|---|
| find / union (both optimisations) | O(α(n)) ≈ O(1) | — |
| Space | — | O(n) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Count connected components
Write count_components(n, edges) for an undirected graph with nodes 0..n-1. Return the number of connected components. Union-find is ideal.