Union-Find (Disjoint Set Union) ndjek një ndarje të elementeve në bashkësi disjunkte dhe suporton dy operacione pothuajse O(1): find (në cilën bashkësi është x?) dhe union (bashko dy bashkësi). Është i shkëlqyer për pyetje të lidhshmërisë.
Sédo bashkësi është një pemë me një përfaqësues rrënjë. Me dhe , operacionet funksionojnë në kohë pothuajse konstante (inverse Ackermann, α(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 dhe union by rank, pemët degradojnë në zinxhira O(n). Nuk suporton ndarjen efikase të bashkësive.
Union-find përgjigjet në pyetjen "a janë këta dy gjëra të lidhura?" në shkallë masive me pothuajse asnjë kosto.
Eshtë motori brenda MST të Kruskalit dhe shumë algoritme të grafeve dhe grupimeve.
Dy optimizazimet e tij janë një mësim i paharrueshëm se si tregimet e vogla strukturore japin performancë pothuajse konstante.