A disjoint-set (union-find) iżomm l-elementi miqsuma f'gruppi li m'għandhomx naqsa u jirrispondu għal "dawn it-tnejn huma fl-istess grupp?" u "" f'. B' u , iż-żewġ operazzjonijiet joħolqu f' — effettivament O(1) (α hija l-inverza tal-funzjoni ta' Ackermann).
Kull sett huwa siġra; l-għerq huwa r-rappreżentant tas-sett. find jimxi sal-għerq; union jgħaqqad għerq waħed taħt ieħor.
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
before: a->b->c->root after: a->root, b->root, c->root
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0]*n
def find(self, x): # path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # halve path
x = self.parent[x]
return x
def union(self, a, b): # union by rank
ra, rb = self.find(a), self.find(b)
if ra == rb: return False
if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
return True
| Operazzjoni | Ħin (bil-ħininn l-ottimizzazzjonijiet) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |
Union-find tissolvi problemi ta' gruppazzjoni u konnettività li b'mod ieħor ikollhom bżonn traversals ripetuti O(n) tal-grafu, u tħawwidhom għal O(1) kważi għal kull mistoqsija.
Hija għodda ta' għalfejn kull meta trid tgħaqqad gruppi b'mod inkrementali u ttestja l-konnettività — suġġett frekwenti f'intervisti ta' livell għoli.