0Pricing
Competitive Programming Academy · Ders

Yol Sıkıştırmalı DSU

Birleştirme ve bulma işlemlerini neredeyse sabit zamanda yapın.

Yol Sıkıştırmalı DSU, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.

DSU Neyi İzler

Ayrık Kümeler Birliği, öğeleri kesişmeyen kümeler halinde gruplandırır; böylece iki şeyin zaten birlikte olup olmadığını sorabilirsiniz. 🤝

Ağaçlar Olarak Kümeler

DSU her kümeyi bir ağaç olarak saklar. Her öğe bir üst düğümü gösterir; en üst düğüm olan kök, grubun benzersiz adıdır.

Üst Düğüm Dizisi

Tüm bu bağlantıları tek bir dizide tutarsınız. Her öğeyi başlangıçta kendi üst düğümü olarak ayarlayın; bu, her öğenin başlangıçta tek başına bir kümede olduğu anlamına gelir.

parent = list(range(n))

Kökü Bulma

find işlemi, bir öğe kendisini gösterene kadar üst düğüm bağlantıları boyunca yukarı çıkar. Kendini gösteren bu düğüm, kümeyi tanımlayan köktür.

while parent[x] != x:
    x = parent[x]

Uzun Zincirler Sorun Yaratır

Dikkat edilmezse kümeler uzun ve ince zincirler oluşturabilir. Bu durumda find düğüm düğüm ilerler ve tek bir sorgu O(n) maliyetine çıkabilir; bu da çok yavaştır.

Yol Sıkıştırma Devreye Giriyor

Yol sıkıştırma bunu düzeltir: kökü bulurken ziyaret edilen her düğümü doğrudan köke bağlarsınız ve ağacı bir sonraki kullanım için düzleştirirsiniz. ⚡

Özyinelemeli Sıkıştırma

En temiz yol özyineleme kullanmaktır. Kökü bulun, ardından geri dönmeden önce onu parent[x] içine kaydedin; böylece bağlantı kalıcı olarak kısalır.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

İki Öğe Aynı Kümede mi

İki öğenin bağlantılı olup olmadığını test etmek için köklerini karşılaştırın. find(a) ile find(b) eşitse aynı gruptadırlar; aksi halde hâlâ ayrıdırlar.

if find(a) == find(b):
    print("connected")

İki Kümeyi Birleştirme

union işlemi, köklerden birini diğerinin altına bağlayarak grupları birleştirir. Tek bir satır, iki ağacın tamamını tek bir kümede birleştirir.

def union(a, b):
    parent[find(a)] = find(b)

Neden Bu Kadar Hızlı

Yalnızca sıkıştırmayla işlemler yaklaşık O(log n) itfa edilmiş maliyetle çalışır; sıralamayla birlikte kullanıldığında sorgu başına süre sabite yaklaşır.

DSU'nun Parladığı Yerler

DSU, bağlantılılık sorularını çözer: arkadaş çevreleri, ağ bileşenleri ve Kruskal'ın kapsayan ağacı hızlı find ve union işlemlerine dayanır. 🌐

Hızlı Kontrol

Yol sıkıştırmanın gerçekte neyi değiştirdiğini düşünün.

Tekrar

Bir DSU oluşturdunuz: bir üst düğüm dizisi, kökü bulmak için find ve kümeleri birleştirmek için union. Yol sıkıştırma, yapıyı son derece hızlı tutar. Harika iş! 🎉

Sıkça Sorulan Sorular

“Yol Sıkıştırmalı DSU” dersi ücretsiz mi?

Evet — “Yol Sıkıştırmalı DSU” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.

“Yol Sıkıştırmalı DSU” dersinde ne öğreneceğim?

Birleştirme ve bulma işlemlerini neredeyse sabit zamanda yapın. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.

“Yol Sıkıştırmalı DSU” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

  1. Yol Sıkıştırmalı DSU
  2. Rütbeye Göre Birleştirme ve Bileşenler
  3. Kruskal'ın Minimum Örtücü Ağacı
  4. Yığınla Prim'in MST'si
← Competitive Programming Academy Sayfasına Dön