Union-Find (Disjoint Set Union) отслеживает разбиение элементов на непересекающиеся множества и поддерживает две операции, работающие почти за O(1): find (в каком множестве находится x?) и union (объединить два множества). Она отлично справляется с запросами связности.
Каждое множество — это дерево с корневым представителем. С использованием и операции работают за почти постоянное время (обратная функция Аккермана, α(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
Без сжатия пути и объединения по рангу деревья деградируют в цепи с временем O(n). Не поддерживает эффективное разделение множеств.
Union-find отвечает на вопрос «соединены ли эти два элемента?» в массивных масштабах практически без затрат.
Она — движок внутри алгоритма Крускала и многих алгоритмов на графах и кластеризации.
Её две оптимизации — поучительный урок о том, как малые структурные трюки дают почти постоянное время выполнения.