Apa iku struktur disjoint-set (union-find) kanthi path compression lan union by rank?

Question

Accepted Answer

A **disjoint-set** (union-find) nglacak elemen-elemen sing dipilah dadi klompok-klompok sing ora padha lan njawab "**apa rong elemen iki ana ing klompok sing padha?**" lan "**gabung rong klompok**" ing **wektu meh-konstan**. Kanthi **path compression** lan **union by rank**, loro-lorone operasi kasebut mlaku ing **O(α(n))** — efektif O(1) (α yaiku inverse Ackermann function).

## Cara kerjane

Saben set yaiku wit; **root** yaiku wakil sete. `find` mlaku menyang root; `union` ngikat siji root ing ngisor liyane.

```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
```

## Code

```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
```

| Operation | Wektu (kanthi loro-lorone optimisasi) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Penggunaan umum

- **Kruskal's MST** — gabung komponen tanpa nggawe siklus.
- **Connected components** ing graf utawa grid.
- **Dynamic connectivity** lan masalah jaringan/perkolasi.

## Kenapa penting

Union-find ngatasi masalah pengelompokan lan konektivitas sing yadyan butuh O(n) graph traversal sing isa diulang-ulang, nanging bisa dikompres dadi meh-O(1) saben pitakon.

Iku alat sing wajib dianggo kapan wae sampeyan kudu nggabung set kanthi bertahap lan nggawe tes konektivitas — topik interview tingkat senior sing asring kena.