Yol sıkıştırması ve rütbeye göre birleştirme ile ayrık küme (union-find) yapısı nedir?

Question

Accepted Answer

**Ayrık-küme** (union-find), öğelerin kesişmeyen gruplara bölünmesini izler ve "**bu ikisi aynı grupta mı?**" ve "**iki grubu birleştir**" sorularına **neredeyse sabit zaman**da yanıt verir. **Yol sıkıştırması** ve **rütbeye göre birleştirme** ile her iki işlem de **O(α(n))**'de çalışır — etkili olarak O(1) (α ters Ackermann fonksiyonudur).

## Nasıl çalışır

Her küme bir ağaç; **kök**, kümenin temsilcisidir. `find` köke doğru yürür; `union` bir kökü diğerinin altına bağlar.

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## Kod

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| İşlem | Zaman (her iki optimizasyonla) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Yaygın kullanımlar

- **Kruskal MST** — döngü oluşturmadan bileşenleri birleştir.
- **Bağlı bileşenler** bir grafta veya ızgarada.
- **Dinamik bağlantı** ve ağ/sızma sorunları.

## Neden önemli

Union-find, aksi takdirde tekrarlanan O(n) grafik geçişlerine ihtiyaç duyacak gruplandırma ve bağlantı sorunlarını çözer ve bunları sorgu başına neredeyse O(1)'e indirger.

Kümeleri kademeli olarak birleştirmeniz ve bağlantıyı test etmeniz gereken her zaman vazgeçilmez bir araçtır — sık karşılaşılan üst düzey mülakat konusu.