Kas yra union-find ir kur jis naudojamas?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) stebi elementų skaidymą į **atskiras aibes** ir palaiko dvi beveik-O(1) operacijas: **find** (kurioje aibėje yra x?) ir **union** (sujungti dvi aibes). Jis puikiai tinka **ryšio** užklausoms.

## Idėja

Kiekviena aibė yra medis su atstovine šaknimi. Su **kelio suspaudimu** ir **sąjunga pagal rangą/dydį**, operacijos veikia beveik pastovia **amortizuota** laiku (atvirkštinis Ackermann, α(n)).

## Pavyzdys

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

## Sudėtingumas

- **find / union:** O(α(n)) ≈ O(1) amortizuota. **Atmintis:** O(n).

## Taikymai

- **Kruskal's MST** — ciklo aptikimas pridedant briaunas.
- **Sujungti komponentai** / dinaminė ryšio nustatymas.
- **Ciklo aptikimas** nenukreiptuose grafuose.
- **Perkolacija**, vaizdo segmentacija, paskyros/tinklo sujungimas.

## Spąstai

Be kelio suspaudimo ir sąjungos pagal rangą/dydį, medžiai gali pablogėti iki O(n) grandinių. Jis nepalaiko efektyvios aibių *skaidymo*.

## Kodėl tai svarbu

Union-find atsakymą į klausimą "ar šie du dalykai yra susieti?" suteikia milžinišku masteliu beveik be jokios kainos.

Jis yra Kruskal's MST vidinis variklis ir daugelio grafinių bei klasterizavimo algoritmų šerdis.

Jo dvi optimizacijos yra atmintina pamoka apie tai, kaip maži struktūriniai triukai suteikia beveik pastovaus laiko našumą.