Disjoint set temelleri
Adım 1/8
Altı eleman, her biri kendi ebeveyni (parent). Bir şey birleşmeden önce bu altı ayrı grup demek.
Fikir
Tek bir dizi tut: parent[x], x'in gösterdiği eleman. Pointer'ları (işaretçi) takip edersen kendini gösteren bir elemanda durursun — bu kök, yani grubun adı.
find o köke kadar yukarı çıkar. union iki kökü de bulur ve birini diğerinin altına asar; iki grubu tek bir atamayla birleştirir.
Gerçek hayattan örnek
Yüzleri gruplayan bir fotoğraf kütüphanesi düşün. İki grubun aynı kişi olduğunu onayladığında kütüphane her fotoğrafı yeniden etiketlemez — bir grubu diğerine yönlendirir. Sonradan "aynı kişi mi?" diye sormak, varılan iki etiketi karşılaştırmaktan ibarettir.
Kod
Sıra sende
Boşluğu doldur.
parent = [0, 0, 2, 2]
def find(x):
while parent[x] ___ x:
x = parent[x]
return x
print(find(1), find(3)) # 0 2Mini quiz
1 / 3