Ayrık-küme (union-find), öğelerin kesişmeyen gruplara bölünmesini izler ve "bu ikisi aynı grupta mı?" ve "iki grubu birleştir" sorularına da yanıt verir. ve ile her iki işlem de 'de çalışır — etkili olarak O(1) (α ters Ackermann fonksiyonudur).
Ayrık-küme (union-find), öğelerin kesişmeyen gruplara bölünmesini izler ve "bu ikisi aynı grupta mı?" ve "iki grubu birleştir" sorularına da yanıt verir. ve ile her iki işlem de 'de çalışır — etkili olarak O(1) (α ters Ackermann fonksiyonudur).
Her küme bir ağaç; kök, kümenin temsilcisidir. find köke doğru yürür; union bir kökü diğerinin altına bağlar.
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
| İşlem | Zaman (her iki optimizasyonla) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |
Union-find, aksi takdirde tekrarlanan O(n) grafik geçişlerine ihtiyaç duyacak gruplandırma ve bağlantı sorunlarını çözer ve bunları sorgu başına neredeyse O(1)'e indirger.
Kümeleri kademeli olarak birleştirmeniz ve bağlantıyı test etmeniz gereken her zaman vazgeçilmez bir araçtır — sık karşılaşılan üst düzey mülakat konusu.
Junior'dan Senior'a detaylı cevaplarla bir BT mülakat soruları kütüphanesi.
Bağış Yap