Co to jest union-find i gdzie się go używa?

Question

IT Interview Practice · Accepted Answer

**Union-Find** (Disjoint Set Union) śledzi podział elementów na **rozłączne zbiory** i wspiera dwie operacje o złożoności prawie O(1): **find** (w jakim zbiorze znajduje się x?) i **union** (połącz dwa zbiory). Doskonale sprawdza się w zapytaniach o **łączność**.

## Idea

Każdy zbiór jest drzewem z reprezentacyjnym korzeniem. Przy zastosowaniu **path compression** i **union by rank/size**, operacje działają w prawie stałym **amortyzowanym** czasie (odwrotna funkcja Ackermanna, α(n)).

## Przykład

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

## Złożoność

- **find / union:** O(α(n)) ≈ O(1) amortyzowana. **Pamięć:** O(n).

## Zastosowania

- **Kruskal MST** — detekcja cykli podczas dodawania krawędzi.
- **Połączone komponenty** / dynamiczna łączność.
- **Detekcja cykli** w grafach nieskierowanych.
- **Perkolacja**, segmentacja obrazu, łączenie kont/sieci.

## Pułapki

Bez path compression i union by rank drzewa degradują się do łańcuchów O(n). Nie wspomaga efektywnego *dzielenia* zbiorów.

## Dlaczego to ważne

Union-find odpowiada na pytanie "czy te dwie rzeczy są połączone?" na masywną skalę niemal bez kosztów.

Jest silnikiem napędzającym algorytm Kruskala MST i wiele algorytmów grafowych i klastrowania.

Jego dwie optymalizacje stanowią pouczającą lekcję o tym, jak małe sztuczki strukturalne dają wydajność prawie stałą w czasie.

Idea

Przykład

Złożoność

Zastosowania

Pułapki

Dlaczego to ważne

Powiązane pytania