Mi az egy szétválasztott halmaz (union-find) szerkezet útösszenyomítással és rangok szerinti unióval?

Question

Accepted Answer

Egy **szétválasztott halmaz** (union-find) nyomon követi az elemeket, amelyek nem átfedő csoportokra vannak particionálva, és "**ezek a kettő ugyanabban a csoportban vannak?**" és "**két csoport egyesítése**" kérdésekre válaszol **közel állandó időben**. Az **útösszenyomítás** és a **rangok szerinti unió** segítségével mindkét operáció **O(α(n))** időben fut — gyakorlatilag O(1) (α az inverz Ackermann-függvény).

## Hogyan működik

Minden halmaz egy fa; a **gyökér** a halmaz reprezentánsa. A `find` felhalad a gyökerig; az `union` egy gyökeret egy másik alá kapcsol.

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

## Kód

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

| Művelet | Idő (mindkét optimalizációval) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Gyakori felhasználások

- **Kruskal MST** — komponensek egyesítése ciklusok nélkül.
- **Összekapcsolt komponensek** egy gráfban vagy rácsban.
- **Dinamikus összekapcsolódás** és hálózati/perkolációs problémák.

## Miért fontos

A union-find olyan csoportosítási és összekapcsolódási problémákat old meg, amelyek egyébként ismételt O(n) gráfbejárásokat igényelnek, szinte O(1)-re csökkentve lekérdezésről lekérdezésre.

Elengedhetetlen eszköz, ha inkrementálisan össze kell fésülni halmazokat és tesztelni kell az összekapcsolódást — gyakori senior szintű interjútéma.