Path compression
Adım 1/10
derinlik4atlama0
Bir zincir: 0, 1'i gösterir, 1 de 2'yi, 4'e kadar. Her find hepsini baştan yürümek zorunda.
Fikir
Union işlemleri uzun bir zincir kurabilir; sonra her find o zinciri baştan dolaşır. Oysa ilk dolaşma cevabı çoktan öğrenmişti.
O yüzden aynı yol üzerinden ikinci bir geçiş yap ve her düğümü (node) doğrudan köke yönlendir. Bir kez bedelini ödediğin yol, ondan sonra onu kullanan herkes için düz kalır.
Gerçek hayattan örnek
Seni yardım edebilecek tek kişiye ulaştırmadan önce üç departmandan geçiren bir telefon menüsü düşün. İkinci seferde doğrudan o kişinin numarasını ararsın. Kimse rotayı yeniden çıkarmaz, çünkü rota not etmeye değerdi.
Kod
Sıra sende
Bu kod ne yazdırır?
parent = [1, 2, 2]
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root:
parent[x], x = root, parent[x]
return root
find(0)
print(parent)Mini quiz
1 / 3