Apa itu union-find dan di mana ia digunakan?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) melacak partisi elemen ke dalam **himpunan-himpunan terpisah** dan mendukung dua operasi hampir-O(1): **find** (x berada di himpunan mana?) dan **union** (gabungkan dua himpunan). Ini unggul dalam pertanyaan **konektivitas**.

## Idenya

Setiap himpunan adalah pohon dengan akar perwakilan. Dengan **path compression** dan **union by rank/size**, operasi berjalan dalam waktu **amortized** hampir-konstan (inverse Ackermann, α(n)).

## Contoh

```python
class UnionFind:
    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]]  # compress
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## Kompleksitas

- **find / union:** O(α(n)) ≈ O(1) amortized. **Ruang:** O(n).

## Aplikasi

- **Kruskal's MST** — deteksi siklus saat menambahkan tepi.
- **Komponen terhubung** / konektivitas dinamis.
- **Deteksi siklus** dalam grafik tak berarah.
- **Perkolasi**, segmentasi gambar, penggabungan akun/jaringan.

## Jebakan

Tanpa path compression dan union by rank, pohon-pohon menurun menjadi rantai O(n). Ini tidak mendukung *pemisahan* himpunan yang efisien.

## Mengapa ini penting

Union-Find menjawab "apakah kedua hal ini terhubung?" dalam skala besar dengan hampir tanpa biaya.

Ini adalah mesin di dalam Kruskal's MST dan banyak algoritma grafik dan clustering.

Dua optimisasinya adalah pelajaran yang berkesan tentang bagaimana trik-trik struktural kecil memberikan kinerja waktu hampir-konstan.