Kaj je union-find in kje se uporablja?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) sledi particiji elementov v **disjunktne množice** in podpira dve operaciji skoraj O(1): **find** (v kateri množici je x?) in **union** (združi dve množici). Odličen je za poizvedbe **povezanosti**.

## Ideja

Vsaka množica je drevo s predstavnikom koren. Z **path compression** in **union by rank/size** se operacije izvajajo v skoraj konstantnem **amortiziranem** času (inverz Ackermanna, α(n)).

## Primer

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

## Kompleksnost

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

## Aplikacije

- **Kruskalov MST** — detekcija ciklov pri dodajanju robov.
- **Povezane komponente** / dinamična povezanost.
- **Detekcija ciklov** v neusmerjenih grafih.
- **Perkolacija**, segmentacija slik, združevanje računov/omrežij.

## Pasti

Brez path compression in union by rank se drevesa degradirajo v O(n) verige. Ne podpira učinkovitega *deljenja* množic.

## Zakaj je to pomembno

Union-find odgovori na vprašanje "sta ti dve stvari povezani?" v massive obsegu z skoraj ničnimi stroški.

Je motor znotraj Kruskalovega MST in številnih grafovnih in grubirnih algoritmov.

Njegovi dve optimizaciji sta nepozabna lekcija o tem, kako majhne strukturne trike prinesejo skoraj konstantno-časovno zmogljivost.