Union-find

Ayrık kümeleri birleştiren union-find veri yapısını öğrenirsin.

Union-find, bir grafiğin düğümlerini kümeler halinde izler. find(x) x'in kökünü bulur; union(x, y) iki küreyi birleştirir.

Bu yapı, Kruskal'ın döngü denetiminde kullanılır. Her düğüm bir ata (parent) gösterir; kök olan düğüm kendine işaret eder.

Ata dizisi

Her düğümün bir atası (parent) vardır. Başlangıçta her düğüm kendi atasıdır: parent[i] = i. Birleşme olunca ata güncellenir.

Kök bulma, ata zincirini takip eder: while parent[x] != x: x = parent[x]. Bu döngü kökü bulana kadar devam eder.

init_parent(n) yaz. Her düğümün kendisi olduğu ata dizisini döndür. print(init_parent(4)) ile yazdır.

Örnek çözümü göster

def init_parent(n):
    # Ata dizisini döndür
    return list(range(n))
print(init_parent(4))

Sıradaki ders: Trie