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;
}
}Union-Find (Disjoint Set Union) utrzymuje podział elementów na rozłączne zbiory i wspiera:
Dwie kluczowe optymalizacje:
…sprawiają, że operacje są praktycznie stałokosztowe dla realnych danych: O(alpha(n)) amortyzowane (odwrotność funkcji Ackermanna, rośnie ekstremalnie wolno).
class DSU {
private parent: number[]
private size: number[]
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i)
this.size = Array.from({ length: n }, () => 1)
}
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) {
let ra = this.find(a)
let rb = this.find(b)
if (ra === rb) return
if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]
this.parent[rb] = ra
this.size[ra] += this.size[rb]
}
}