Union-Find (Disjoint Set)
Week 10
What it is
Tracks which elements belong to the same connected component. Supports two operations in near O(1) amortized.
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = Array(n).fill(0);
this.components = n;
}
find(x) {
if (this.parent[x] !== x)
this.parent[x] = this.find(this.parent[x]); // path compression
return this.parent[x];
}