Apa itu struktur disjoint-set (union-find) dengan kompresi jalur dan union by rank?

Question

Accepted Answer

Sebuah **disjoint-set** (union-find) melacak elemen yang dipartisi menjadi grup yang tidak tumpang tindih dan menjawab "**apakah keduanya berada dalam grup yang sama?**" dan "**gabungkan dua grup**" dalam **waktu hampir-konstan**. Dengan **kompresi jalur** dan **union by rank**, kedua operasi berjalan dalam **O(α(n))** — efektif O(1) (α adalah fungsi invers Ackermann).

## Cara kerjanya

Setiap set adalah pohon; **akar** adalah perwakilan set. `find` berjalan ke akar; `union` menghubungkan satu akar di bawah yang lain.

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

## Kode

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

| Operasi | Waktu (dengan kedua optimasi) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Penggunaan umum

- **MST Kruskal** — gabungkan komponen tanpa membentuk siklus.
- **Komponen terhubung** dalam graf atau grid.
- **Konektivitas dinamis** dan masalah jaringan/perkolasi.

## Mengapa ini penting

Union-find memecahkan masalah pengelompokan dan konektivitas yang sebaliknya memerlukan traversal graf O(n) berulang, mengecilkannya menjadi hampir O(1) per kueri.

Ini adalah alat yang sangat diperlukan setiap kali Anda harus secara inkremental menggabungkan set dan menguji konektivitas — topik wawancara tingkat senior yang sering muncul.