Što je union-find i gdje se koristi?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) prati particiju elemenata u **disjunktne skupove** i podržava dvije gotovo-O(1) operacije: **find** (u kojem skupu je x?) i **union** (spoji dva skupa). Odličan je za upite **povezanosti**.

## Ideja

Svaki skup je stablo s reprezentativnim korijenski čvorom. S **path compression** i **union by rank/size**, operacije se izvršavaju u gotovo konstantnom **amortiziranom** vremenu (inverse Ackermann, α(n)).

## Primjer

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

## Složenost

- **find / union:** O(α(n)) ≈ O(1) amortiziranog. **Prostor:** O(n).

## Primjene

- **Kruskalov MST** — detekcija ciklusa tijekom dodavanja bridova.
- **Povezane komponente** / dinamička povezanost.
- **Detekcija ciklusa** u neusmjerenim grafovima.
- **Perkolacija**, segmentacija slike, spajanje računa/mreža.

## Zamke

Bez path compression i union by rank, stabla se degradiraju na O(n) lance. Ne podržava učinkovito *dijeljenje* skupova.

## Zašto je to važno

Union-Find odgovara na "su li ova dva elementa povezana?" u masivnom mjerilu s gotovo nikakvim troškovima.

To je motor u Kruskalovu MST i mnogim algoritmima za grafove i klasteriranje.

Njegove dvije optimizacije su nezaboravna lekcija kako mali strukturalni trikovi daju gotovo-konstantno vremensku performansu.