Kas yra disjunktinė aibė (union-find) su kelio suspaudimu ir rango sąjunga?

Question

Accepted Answer

**Disjunktinė aibė** (union-find) sekina elementus, suskirstytus į nepersidengiančias grupes, ir atsakinėja į klausimus "**ar šie du yra toje pačioje grupėje?**" ir "**sujungti dvi grupes**" per **beveik konstantą laiką**. Su **kelio suspausimu** ir **rango sąjunga**, abi operacijos vykdomos per **O(α(n))** — faktiškai O(1) (α yra atvirkštinė Ackermann funkcija).

## Kaip tai veikia

Kiekviena aibė yra medis; **šaknis** yra aibės atstovas. `find` eina prie šaknies; `union` sujungia vieną šaknį po kita.

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

## Kodas

```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 | Laikas (su abiem optimizacijomis) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Dažni naudojimo atvejai

- **Kruskalio MST** — sujungti komponentus neformuojant ciklų.
- **Sujungti komponentai** grafe arba tinklelyje.
- **Dinaminis ryšingumas** ir tinklo/perkoliavimo uždaviniai.

## Kodėl tai svarbu

Union-find išsprendžia grupavimo ir ryšingumo uždavinius, kuriems priešingu atveju reikėtų pakartotinių O(n) grafo perėjimu, sutraukdama juos į beveik O(1) per užklausą.

Tai yra pagrindinė priemonė, kai reikia nuosekliai sujungti aibes ir tikrinti ryšingumą — dažna aukšto lygio pokalbio tema.