Apa iku union-find lan ing endi digunakake?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) nlacak partisi elemen menyang **set sing ora nyambung** lan ndhukung rong operasi meh-O(1): **find** (set apa x isine?) lan **union** (gabung rong set). Iku apik banget kanggo query **konektivitas**.

## Ide

Saben set yaiku wit kanthi root wakil. Kanthi **path compression** lan **union by rank/size**, operasi mlaku ing wektu **amortized** meh-konstan (Ackermann terbalik, α(n)).

## Conto

```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. **Papan:** O(n).

## Kagunaan

- **Kruskal's MST** — deteksi siklus nalika nambah sisi.
- **Komponen nyambung** / konektivitas dinamis.
- **Deteksi siklus** ing graf sing ora direktif.
- **Perkolasi**, segmentasi gambar, penggabungan akun/jaringan.

## Jebakan

Sans path compression lan union by rank, wit bisa rusak dadi rantai O(n). Iku ora ndhukung *pemisahan* set kanthi efisien.

## Mengapa penting

Union-find njawab "apa loro bab iki nyambung?" kanthi skala gede lan biaya meh ora ana.

Iku mesin ing mburi Kruskal's MST lan akeh algoritma graf lan clustering.

Rong optimisasi kasebut yaiku pelajaran sing diweningake babagan carane trik struktural cilik ngasilake performa wektune meh-konstan.