0Pricing
DSA Interview Prep · Ders

Yol Sıkıştırmalı DSU

Yol üzerindeki tüm düğümlerin doğrudan köke işaret etmesini sağlayan yol sıkıştırmalı find işlemini uygulayın ve amorti edilmiş neredeyse O(1) find süresine ulaşın.

Yol Sıkıştırmalı DSU, CoddyKit'te ücretsiz bir DSA Interview Prep 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, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Ayrık Küme Birleşimi Nedir?

Ayrık Küme Birleşimi (DSU) veya Birleştirme-Bulma olarak da adlandırılan yapı, ayrık (kesişmeyen) kümelerden oluşan bir koleksiyonu yöneten bir veri yapısıdır. İki temel işlemi destekler: find (x öğesi hangi kümeye aittir?) ve union (x ile y'yi içeren kümeleri birleştirir). DSU, grupların zaman içinde birleştiği ancak hiçbir zaman ayrılmadığı dinamik bağlantılılık problemleri için idealdir.

Her öğe başlangıçta kendi kümesindedir. Kenarları veya ilişkileri işlerken kümeleri birbiriyle birleştiririz. Buradaki zorluk, bunu verimli biçimde yapmaktır; saf uygulamalar işlem başına O(n) maliyetlidir, ancak iyileştirmelerle itfa edilmiş O(1) maliyetine yaklaşırız.

# Naive DSU without optimisations
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own parent

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

Naif Find Sorunu

Naif DSU'da find(x), kendisini gösteren bir düğüme (köke) ulaşana kadar üst düğüm zincirinde yukarı doğru ilerler. Ağaç dengeliyse bu işlem O(log n) sürer. Ancak her zaman ikinci kökü birincinin altına bağlayarak birleştirirsek, uzunluğu n olan bir zincir (yozlaşmış ağaç) oluşturabilir ve her find işleminin O(n) sürmesine neden olabiliriz.

0→1→2→3→4 düğümlerini sırasıyla birleştirmeyi düşünün. 0 düğümündeki find çağrısı zincirin tamamını dolaşmak zorundadır. Yol sıkıştırması ile find işleminin kendisi sırasında ziyaret edilen her düğümün doğrudan kökü göstermesini sağlayarak bu sorunu ortadan kaldırırız.

# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4]  => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4]  => find(0) takes 1 step

parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
    x = parent[x]
    steps += 1
print('Root:', x, 'Steps taken:', steps)

Yol Sıkıştırması: Tek Geçişli Özyinelemeli Yöntem

Yol sıkıştırması, kök bulunduktan sonra yol üzerindeki her düğümün doğrudan kökü gösterecek şekilde güncellenmesini sağlar. Bu düğümlerdeki sonraki find çağrıları O(1) sürer. Özyinelemeli sürüm bunu tek geçişte zarif bir şekilde gerçekleştirir.

Temel fikir şudur: Özyinelemeli çağrı kökü döndürdükten sonra, dönüş yapmadan önce self.parent[x] = root atamasını yaparız. Bu işlem ağacı düzleştirir; arama yolundaki tüm düğümler artık doğrudan kökü gösterir. Bu, bir düğümün ait olduğu kümeyi değiştirmez; yalnızca gelecekteki arama yollarını kısaltır.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)

Yol Sıkıştırması: İki Geçişli Yinelemeli Yöntem

Yol sıkıştırmasının yinelemeli sürümü iki geçiş kullanır: İlk geçiş kökü bulmak için yukarı doğru ilerler; ikinci geçiş ise yoldaki her düğümü yeniden ziyaret ederek üstünü doğrudan kök olacak şekilde günceller. Bu yöntem özyineleme yığını ek yükünü ortadan kaldırır ve Python'ın özyineleme sınırına yakın çok derin ağaçlarda güvenlidir.

Hem özyinelemeli hem de yinelemeli yaklaşımlarda doğruluk değişmez; find yine aynı kökü döndürür. Tek fark, yan etki olarak üst işaretçilerinin güncellenmesidir; bu da bu düğümlerdeki gelecekteki tüm find çağrılarını O(1) hâline getirir.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]          # first pass: find root
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root             # second pass: compress
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False  # already connected

dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
    dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after  find(0):', dsu.parent[:])

Yol Sıkıştırmasının Amortize Edilmiş Karmaşıklığı

Yol sıkıştırması tek başına, m işlemden oluşan bir dizi boyunca işlem başına O(log n) amortize edilmiş süre sağlar. Bir zincir ilk kez dolaşılırken find işlemi pahalı olabilir; ancak zinciri düzleştirerek bu düğümlerdeki sonraki her find işleminin O(1) sürmesini sağlar. Toplam iş, birçok işlem arasında dağıtılır.

Biçimsel çözümlemede potansiyel fonksiyon yöntemi kullanılır: Bir düğümün üstü her kısaldığında DSU'nun potansiyeli azalır ve bu azalma, dolaşma maliyetini karşılar. Dereceye göre birleştirme olmadan yol sıkıştırması tek başına amortize edilmiş O(log n) süre sağlar; bu bile naif O(n) yaklaşımına göre büyük bir iyileştirmedir.

# Demonstrating amortised benefit
import time

def build_chain(n):
    parent = list(range(n))
    for i in range(n - 1):
        parent[i] = i + 1  # chain: 0->1->2->...->n-1
    return parent

n = 1000
parent = build_chain(n)

# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
    root = parent[root]
# Compress
while parent[x] != root:
    nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0])  # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')

Bağlantılı Bileşen Sayısı

Yaygın bir DSU uygulaması, bir grafikteki bağlantılı bileşenleri saymaktır. components sayacını n'e, yani düğüm sayısına, eşit olacak şekilde başlatırız. Her başarılı union işlemi (iki farklı kümenin birleştirilmesi) sayacı 1 azaltır. İşlemlerin sonunda sayaç, birbirinden farklı bileşenlerin sayısını tutar.

Bu yöntem, özellikle kenarlar artımlı olarak (çevrimiçi) geldiğinde, bağlantı sorguları için BFS veya DFS çalıştırmaktan daha verimlidir. DSU, her kenarı ne zaman geldiğinden bağımsız olarak neredeyse O(1) amortize edilmiş sürede işler.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.components = n

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        self.parent[px] = py
        self.components -= 1
        return True

dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
    dsu.union(u, v)
print('Components:', dsu.components)  # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')

Graf Problemleri için DSU: İl Sayısı

İl Sayısı problemi, n×n boyutunda bir komşuluk matrisi verir ve doğrudan veya dolaylı olarak bağlantılı şehirlerden kaç grup bulunduğunu sorar. Bu, DSU'nun temiz bir şekilde çözdüğü bir bağlantılı bileşen problemidir. isConnected[i][j] == 1 olan tüm (i, j) çiftlerini dolaşır ve union(i, j) çağrısını yaparız.

Tüm bağlantılar işlendikten sonra yanıt dsu.components değeridir. Bu yöntem, ziyaret edilmemiş her düğümden BFS çalıştırmaktan daha basit ve hızlıdır; ayrıca önce bir komşuluk listesi oluşturmadan matris gösterimini doğrudan işler.

def find_provinces(isConnected):
    n = len(isConnected)
    parent = list(range(n))

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

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    count = n
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                if union(i, j):
                    count -= 1
    return count

matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix))  # 2: cities {0,1} and {2}

Yol Sıkıştırması Çeşitleri: Yarıya İndirme

İki geçişli sıkıştırmanın yanı sıra yolun yarıya indirilmesi adı verilen daha basit bir tek geçişli yöntem de vardır: Zincirde yukarı doğru ilerlerken her düğümün üstünü, kendi üstü yerine üstünün üstü olacak şekilde ayarlarız. Bu yöntem, ikinci bir geçiş yapmadan her dolaşmada yol uzunluğunu yarıya indirir ve dereceye göre birleştirmeyle birlikte kullanıldığında aynı O(alpha(n)) amortize edilmiş karmaşıklığı sağlar.

Yolun yarıya indirilmesi, özyineleme veya ikinci bir dolaşma gerektirmeyen tek ve temiz bir döngü olduğu için yarışmalı programlamada sıklıkla tercih edilir. Her adımda self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x] çalıştırılır.

class DSUHalving:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # point to grandparent
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
    dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))

Birleştirmelerden Sonra Bağlantıyı Denetleme

İki düğümün connected olup olmadığını (aynı bileşende bulunup bulunmadığını) denetlemek için find(x) == find(y) çağrısını yapın. İkisi de aynı kökü döndürüyorsa aynı bileşendedir. Bu, connected sorgusudur ve yol sıkıştırmasıyla neredeyse O(1) amortize edilmiş sürede çalışır.

Mülakat sorularında bağlantı sorguları çoğu zaman union işlemleriyle iç içe verilir. DSU her ikisini de çevrimiçi olarak yönetir; union işlemleriyle sorguları istediğiniz sırayla dönüşümlü biçimde yapabilirsiniz. Bu özellik, her yapısal değişiklikten sonra yeniden çalıştırılması gereken BFS/DFS gibi durağan grafik algoritmalarından DSU'yu ayırır.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

    def connected(self, x, y):
        return self.find(x) == self.find(y)

dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7))   # True: 0-3-7
print(dsu.connected(0, 5))   # False: different components
print(dsu.connected(1, 5))   # True: 1-5

DSU Uygulamasındaki Yaygın Hatalar

Sık yapılan bir hata, find çağrısını yaptıktan sonra parent değerini yanlış değiştirmektir. Eşitliği denetlemeden önce her iki öğe için de find çağrısını mutlaka yapın; aksi hâlde bir düğümü yanlışlıkla kendi köküyle karşılaştırabilirsiniz. Bir diğer hata da her iki öğe zaten aynı kökü paylaşıyorsa union işleminin hiçbir şey yapmaması gerektiğini unutmaktır.

Python'da özyineleme derinliği sınırı (varsayılan olarak 1000), özyinelemeli find kullanan büyük zincirlerde RecursionError oluşmasına neden olabilir. Derin özyinelemeyi tamamen önlemek için ya yinelemeli iki geçişli sürümü kullanın, ya sınırı sys.setrecursionlimit ile artırın ya da yolun yarıya indirilmesi yöntemini yinelemeli olarak uygulayın.

import sys
sys.setrecursionlimit(10000)  # needed for large recursive DSU

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        # Safe iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same component — do nothing
        self.parent[px] = py
        return True

dsu = DSU(5)
print(dsu.union(0, 1))  # True: merged
print(dsu.union(0, 1))  # False: already merged — no double-counting

DSU Boyut Takibi

Bazı problemlerde yalnızca köke değil, her bileşenin boyutuna da ihtiyaç duyarsınız. Tüm değerleri 1 olarak başlatılmış bir size dizisi ekleyin. İki bileşeni birleştirirken küçük kökün boyutunu büyük köke ekleyin. Böylece herhangi bir union işleminden sonra bileşen boyutu sorgularını O(1) sürede yapabilirsiniz.

Boyut takibi aynı zamanda boyuta göre birleştirmenin temelidir (dereceye göre birleştirmeye alternatif olarak): Küçük ağacı her zaman büyük ağacın kökünün altına bağlayın. Bu, ağaç yüksekliğinin O(log n) kalmasını garanti eder ve dereceye göre birleştirmeyle aynı asimptotik güvenceyi sağlar.

class DSUWithSize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            px, py = py, px           # attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]

    def get_size(self, x):
        return self.size[self.find(x)]

dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
    dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0))  # 3
print('Size of component containing 3:', dsu.get_size(3))  # 2
print('Size of component containing 5:', dsu.get_size(5))  # 1

Hızlı Kontrol

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne ölçüde anladığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: DSU, find ve union işlemleriyle ayrık kümeleri yönetir, yol sıkıştırması, dolaşılan tüm düğümleri doğrudan köke bağlayarak ağacı düzleştirir ve bu, find işleminin neredeyse O(1) amortize edilmiş sürede çalışmasını sağlar. Sırada, ağaçları yukarıdan aşağıya sığ tutarak ters Ackermann sınırına ulaşan dereceye göre birleştirmeyi inceleyeceğiz.

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 DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

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

Yol üzerindeki tüm düğümlerin doğrudan köke işaret etmesini sağlayan yol sıkıştırmalı find işlemini uygulayın ve amorti edilmiş neredeyse O(1) find süresine ulaşın. DSA Interview Prep 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.

DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, 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 DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA Interview Prep 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. Dereceye Göre Birleştirme ve Ters Ackermann Sınırı
  3. Gereksiz Bağlantı ve Çevrim Belirleme
  4. Hesapları Birleştirme ve Bağlantılı Bileşenler
← DSA Interview Prep Sayfasına Dön