0Pricing
Competitive Programming Academy · Ders

Rütbeye Göre Birleştirme ve Bileşenler

Ağaçları düz tutun ve grupları sayın.

Rütbeye Göre Birleştirme ve Bileşenler, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 2. 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.

union Tembel Olabilir

Basit union, bir kökü diğerinin altına bağlar. Dikkatsizce yapıldığında uzun ve yavaş bir ağaç oluşturabilir; bu nedenle kökleri birleştirmek için daha akıllı bir yönteme ihtiyacımız vardır.

Temel Fikir

Dereceye göre union, kısa ağacı her zaman uzun ağacın altına bağlar. Ağaçları sığ tutmak, sonraki her find işlemini hızlandırır. 📏

Derecenin Anlamı

Derece, bir ağacın yüksekliğine ilişkin bir tahmindir. Her öğe derece 0 ile başlar; çünkü tek bir düğümün altında derinlik yoktur.

rank = [0] * n

Kısayı Uzunun Altına Bağlama

İki kökün derecelerini karşılaştırın. Daha küçük dereceli kök çocuk olur; böylece birleşik ağaç mümkün olduğunca düz kalır.

if rank[ra] < rank[rb]:
    parent[ra] = rb

Eşitlikte Dereceyi Artırma

Her iki kökün de derecesi eşitse, yeni kök olarak istediğinizi seçip derecesini bir artırın; çünkü ağaç bir seviye daha büyümüştür.

else:
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

Boyuta Göre union Çeşitlemesi

Yaygın bir alternatif boyuta göre union yaklaşımıdır: küçük kümeyi büyük olanın altına bağlar. Aynı derecede etkilidir ve grup boyutlarını size ücretsiz olarak sağlar.

Bileşenleri Sayma

Her öğe kendi grubunda olduğundan sayıyı n ile başlatın. Başarılı her union iki grubu birleştirerek bir grup oluşturur; bu nedenle sayıyı bir azaltırsınız.

components = n

Etkisiz union İşlemlerini Atlayın

İki öğe zaten aynı kökü paylaşıyorsa union hiçbir şey yapmaz. Sayıyı yalnızca kökleri gerçekten farklı olduğunda azaltın.

if find(a) != find(b):
    union(a, b)
    components -= 1

Derece ve Sıkıştırma

Dereceye göre union ile yol sıkıştırmayı birleştirdiğinizde DSU, ters Ackermann zamanında çalışır; bu da gerçek girdiler için pratikte sabit zamandır. ⚡

İstenince Grup Boyutları

Boyuta göre union kullanıldığında herhangi bir grubun ne kadar büyük olduğunu anında öğrenebilirsiniz: yalnızca o öğenin kökünde saklanan boyutu okuyun.

group = size[find(x)]

Bunun Faydalı Olduğu Yerler

Bileşen sayımı, bir dizi birleştirme çağrısından sonra arkadaş çevrelerinin veya bağlı bölgelerin sayısı gibi klasik soruları yanıtlar. 🌐

Hızlı Kontrol

Bileşen sayacının nasıl değiştiği üzerine düşünün.

Özet

Ağaçları dengeli tutmak için rütbeye göre birleştirmeyi ve bileşen sayılarını ve grup büyüklüklerini izlemeyi öğrendiniz. DSU artık ışık hızında! 🎉

Sıkça Sorulan Sorular

“Rütbeye Göre Birleştirme ve Bileşenler” dersi ücretsiz mi?

Evet — “Rütbeye Göre Birleştirme ve Bileşenler” 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.

“Rütbeye Göre Birleştirme ve Bileşenler” dersinde ne öğreneceğim?

Ağaçları düz tutun ve grupları sayı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 2. dersidir.

“Rütbeye Göre Birleştirme ve Bileşenler” 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