Union-Find maintains disjoint sets with find(x) (representative) and union(a,b) (merge). It’s used for connectivity and Kruskal’s MST; with path compression + union by rank, operations are almost O(1) amortized.
class DSU {
private parent: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
}
find(x: number): number {
if (this.parent[x] === x) return x;
this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(a: number, b: number) {
const ra = this.find(a);
const rb = this.find(b);
if (ra !== rb) this.parent[rb] = ra;
}
}