İçeriğe geç

Disjoint set temelleri

Ders 1 / 4 · 5 dk

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 2

Mini quiz

1 / 3

Bir grubun kökü nasıl tanınır?