Co je union-find a kde se používá?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) sleduje oddíl prvků do **disjunktních množin** a podporuje dvě operace blízké O(1): **find** (v jaké množině je x?) a **union** (sloučení dvou množin). Vyniká v dotazech na **konektivitu**.

## Nápad

Každá množina je strom s reprezentativním kořenem. S **path compression** a **union by rank/size** běží operace v téměř konstantním **amortizovaném** čase (inverzní Ackermannova funkce, α(n)).

## Příklad

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

- **find / union:** O(α(n)) ≈ O(1) amortizováno. **Prostor:** O(n).

## Aplikace

- **Kruskalův MST** — detekce cyklů při přidávání hran.
- **Propojené komponenty** / dynamická konektivita.
- **Detekce cyklů** v neorientovaných grafech.
- **Perkolace**, segmentace obrázků, slučování účtů/sítí.

## Úskalí

Bez path compression a union by rank se stromy degradují na O(n) řetězce. Nepodporuje efektivní *rozdělování* množin.

## Proč to je důležité

Union-find odpovídá na otázku „jsou tyto dvě věci propojeny?