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

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.

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. 📏

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.

İ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.

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.

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.

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.

İ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.

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. ⚡

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.

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. 🌐

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! 🎉