Union-Find (Disjoint Set Union) śledzi podział elementów na rozłączne zbiory i wspiera dwie operacje o złożoności prawie O(1): find (w jakim zbiorze znajduje się x?) i union (połącz dwa zbiory). Doskonale sprawdza się w zapytaniach o łączność.
Każdy zbiór jest drzewem z reprezentacyjnym korzeniem. Przy zastosowaniu i , operacje działają w prawie stałym czasie (odwrotna funkcja Ackermanna, α(n)).
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # compress
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach smaller under larger
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
Bez path compression i union by rank drzewa degradują się do łańcuchów O(n). Nie wspomaga efektywnego dzielenia zbiorów.
Union-find odpowiada na pytanie "czy te dwie rzeczy są połączone?" na masywną skalę niemal bez kosztów.
Jest silnikiem napędzającym algorytm Kruskala MST i wiele algorytmów grafowych i klastrowania.
Jego dwie optymalizacje stanowią pouczającą lekcję o tym, jak małe sztuczki strukturalne dają wydajność prawie stałą w czasie.