Co je struktura disjoint-set (union-find) s kompresí cesty a sjednocením podle hodnosti?

Question

IT Interview Practice · Accepted Answer

**Disjoint-set** (union-find) sleduje prvky rozdělené do nepřekrývajících se skupin a odpovídá na otázky **"jsou tato dvě ve stejné skupině?"** a **"sloučit dvě skupiny"** v **téměř konstantním čase**. S **kompresí cesty** a **sjednocením podle hodnosti** se obě operace spouští v **O(α(n))** — prakticky O(1) (α je inverzní Ackermannova funkce).

## Jak to funguje

Každá množina je strom; **kořen** je zástupce sady. `find` jde ke kořenu; `union` spojuje jeden kořen pod druhý.

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

## Code

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

| Operace | Čas (s oběma optimalizacemi) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Běžné použití

- **Kruskalův MST** — sloučit komponenty bez vytváření cyklů.
- **Připojené komponenty** v grafu nebo mřížce.
- **Dynamická konektivita** a problémy sítě/perkolace.

## Proč na tom záleží

Union-find řeší problémy seskupování a konektivity, které by jinak vyžadovaly opakované O(n) průchody grafu, čímž je zkolabuje na téměř O(1) na dotaz.

Je to preferovaný nástroj, kdykoli musíte postupně slučovat sady a testovat konektivitu — časté téma v rozhovorech na úrovni senior.

Jak to funguje

Code

Běžné použití

Proč na tom záleží

Související otázky