Mikä on disjoint-set (union-find) rakenne polun tiivistymisen ja union by rank -optimoinneilla?

Question

Accepted Answer

**Disjoint-set** (union-find) seuraa elementtejä, jotka on jaettu ei-päällekkäisiin ryhmiin, ja vastaa kysymyksiin **"ovatko nämä kaksi samassa ryhmässä?"** ja **"yhdistää kaksi ryhmää"** **lähes vakioajassa**. **Polun tiivistymisen** ja **union by rank** -optimoinneilla molemmat operaatiot toimivat **O(α(n))** ajassa — käytännössä O(1) (α on käänteinen Ackermannin funktio).

## Miten se toimii

Jokainen joukko on puu; **juuri** on joukon edustaja. `find` kävtelee juurelle; `union` yhdistää yhden juuren toisen alle.

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

| Operaatio | Aika (molemmilla optimoinneilla) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Yleiset käyttötapaukset

- **Kruskalin MST** — yhdistä komponentit ilman syklien muodostamista.
- **Yhdistetyt komponentit** graafissa tai ruudukossa.
- **Dynaaminen yhteyden testaaminen** ja verkon/perkolaation ongelmat.

## Miksi sillä on merkitystä

Union-find ratkaisee ryhmittely- ja yhteysongelmia, jotka muuten vaatisivat toistettuja O(n) graafin läpikäyntejä, supistamalla ne lähes O(1):een per kysely.

Se on perustyökalu aina, kun joudut inkrementaalisesti yhdistämään joukkoja ja testaamaan yhteyttä — usein esiintyvä aihe senior-level haastatteluissa.