Özet - İleri veri yapıları

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.

Örnek çözümü göster

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))

Kendini test et

Union-find neyi izler?
- Tek düğümü
- Kenar ağırlığını
- Aralıkları
- Kümeleri
Cevabı göster

Kümeleri — Union-find kümeleri izler.

find döngüsü

while parent[x] ____ x:

Cevabı göster

while parent[x] != x:

Özet - İleri veri yapıları: kavramları eşleştir

union-find

Kümeler
trie

Önekler
segment tree

Aralıklar
parent

Ata

Sıradaki ders: Meydan okuma 1

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler