Što je disjunktni skup (union-find) struktura s kompresijom putanje i unijom po rangu?

Question

Accepted Answer

**Disjunktni skup** (union-find) prati elemente podijeljene u nepreklapajuće grupe i odgovara na "**jesu li ova dva u istoj grupi?**" i "**spoji dvije grupe**" u **gotovo konstantnom vremenu**. S **kompresijom putanje** i **unijom po rangu**, obje operacije izvršavaju se u **O(α(n))** — učinkovito O(1) (α je inverzna Ackermannova funkcija).

## Kako funkcionira

Svaki skup je stablo; **korijen** je predstavnik skupa. `find` ide do korijena; `union` povezuje jedan korijen ispod drugoga.

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

## Kod

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

| Operacija | Vrijeme (s obje optimizacije) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Česta korištenja

- **Kruskalov MST** — spajanje komponenti bez stvaranja ciklusa.
- **Povezane komponente** u grafu ili mreži.
- **Dinamička povezanost** i problemi mreže/perkolacije.

## Zašto je to važno

Union-find rješava probleme grupiranja i povezanosti koji bi inače zahtijevali ponavljajuće O(n) prolazake grafa, kolapsujući ih na gotovo O(1) po upitu.

To je neophodan alat svaki put kada trebate inkrementalno spajati skupove i testirati povezanost — česta tema intervjua na razini seniora.