Apakah itu union-find dan di mana ia digunakan?

Question

Accepted Answer

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

## Ideanya

Setiap set adalah pohon dengan akar perwakilan. Dengan **kompresi jalur** dan **gabung menurut pangkat/ukuran**, operasi berjalan dalam waktu **amortisasi** hampir konstan (kebalikan 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) amortisasi. **Ruang:** O(n).

## Aplikasi

- **MST Kruskal** — deteksi siklus saat menambah tepi.
- **Komponen terhubung** / konektivitas dinamis.
- **Deteksi siklus** dalam graf tak terarah.
- **Perkolasi**, segmentasi citra, penggabungan akun/jaringan.

## Jebakan

Tanpa kompresi jalur dan gabung menurut pangkat/ukuran, pohon merosot menjadi rantai O(n). Tidak mendukung *pemisahan* set yang efisien.

## Mengapa penting

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

Ini adalah mesin di dalam MST Kruskal dan banyak algoritma graf dan pengelompokan.

Dua optimisasi ini adalah pelajaran yang berkesan tentang bagaimana trik struktural kecil menghasilkan kinerja waktu hampir konstan.