Union-Find (Disjoint Set Union) realiza un seguimiento de una partición de elementos en conjuntos disjuntos y admite dos operaciones casi O(1): find (¿en qué conjunto está x?) y union (fusionar dos conjuntos). Destaca en consultas de conectividad.
Cada conjunto es un árbol con una raíz representativa. Con y , las operaciones se ejecutan en tiempo casi constante (Ackermann inverso, α(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
Sin path compression y union by rank, los árboles se degradan a cadenas O(n). No admite división eficiente de conjuntos.
Union-find responde a "¿están conectadas estas dos cosas?" a gran escala con casi ningún costo.
Es el motor dentro de MST de Kruskal y muchos algoritmos de grafos y clustering.
Sus dos optimizaciones son una lección memorable sobre cómo pequeños trucos estructurales producen rendimiento casi de tiempo constante.