Union-Find (DSU) utrzymuje rozłączne zbiory operacjami find(x) (reprezentant) i union(a,b) (scalenie). Używa się go do spójności i w algorytmie Kruskala; z path compression + union by rank operacje są prawie O(1) amortyzowane.
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;
}
}