Özet - İleri veri yapıları
- Algoritmalar kursu
- İleri seviye
- Ders 52/56
- 4 dk
Union-find ile küme birleştirme yazdıran mini görev yaparsın.
Özet - İleri veri yapıları
Bu grupta union-find, trie ve segment tree olmak üzere üç ileri veri yapısını öğrendin. Her biri farklı bir amaca hizmet eder: kümeler, önekler, aralıklar.
Şimdi union-find'ı derinleştiren bir fonksiyon yazacaksın. Bu özet, grubun ilk kavramını tek bir kodda birleştirir.
Uygulama count_sets fonksiyonu
count_sets(n) yaz. init_parent hazır; union(0,1) ve union(2,3) yap, ayrı kök sayısını döndür. print(count_sets(4)) ile 2 yazdır.
Başlangıç kodu
def init_parent(n):
# Ata dizisini döndür
return list(range(n))
def count_sets(n):
# Birleşme sonrası ayrı küme sayısını bulÖrnek çözüm
def init_parent(n):
# Ata dizisini döndür
return list(range(n))
def count_sets(n):
# Birleşme sonrası ayrı küme sayısını bul
parent = init_parent(n)
def find(x):
while parent[x] != x:
x = parent[x]
return x
def union(x, y):
parent[find(x)] = find(y)
union(0, 1)
union(2, 3)
roots = set(find(i) for i in range(n))
return len(roots)
print(count_sets(4))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Union-find neyi izler?
- Tek düğümü
- Kenar ağırlığını
- Aralıkları
- Kümeleri Doğru cevap
Açıklama: Union-find kümeleri izler.
2 find döngüsü
Soru
while parent[x] ____ x:
Cevap
while parent[x] != x:Açıklama: != doğru.
3 Özet - İleri veri yapıları: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
union-find |
Kümeler |
trie |
Önekler |
segment tree |
Aralıklar |
parent |
Ata |