Kaj je disjunktna množica (union-find) s stiskanjem poti in zbrajanjem po rangu?

Question

Accepted Answer

**Disjunktna množica** (union-find) sledi elementom, razdeljenim v neprekrivajočih se skupinah, in odgovarja na "**sta ta dva v isti skupini?**" in "**združi dve skupini**" v **skoraj konstantnem času**. Z **stiskanjem poti** in **zbrajanjem po rangu** obe operaciji tečeta v **O(α(n))** — praktično O(1) (α je inverzna Ackermannova funkcija).

## Kako deluje

Vsaka množica je drevo; **korjen** je predstavnik množice. `find` hodi do korjena; `union` poveže en korjen pod drugega.

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

## Koda

```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 | Čas (z obema optimizacijama) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Pogosta uporaba

- **Kruskalov MST** — združi komponente brez oblikovanja ciklov.
- **Povezane komponente** v grafu ali mreži.
- **Dinamična povezanost** in problemi omrežja/perkolacije.

## Zakaj je to pomembno

Union-find rešuje probleme združevanja in povezanosti, ki bi sicer potrebovali ponavljajoče se O(n) prehode grafov, in jih skrči na skoraj O(1) na poizvedbo.

Je osnovni pripomoček, kadar mora te postopoma združevati množice in preverjati povezanost — pogosta tema na seniorskih intervjujih.