Vad är en disjunkt-mängd (union-find) struktur med vägkomprimering och union efter rang?

Question

Accepted Answer

En **disjunkt-mängd** (union-find) spårar element partitionerade i icke-överlappande grupper och besvarar "**är dessa två i samma grupp?**" och "**slå samman två grupper**" i **nästan konstant tid**. Med **vägkomprimering** och **union efter rang** körs båda operationerna i **O(α(n))** — praktiskt O(1) (α är den inversa Ackermann-funktionen).

## Hur det fungerar

Varje mängd är ett träd; **roten** är mängdens representant. `find` går till roten; `union` kopplar en rot under en annan.

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

## Kod

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

| Operation | Tid (med båda optimeringarna) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Vanliga användningar

- **Kruskals MST** — slå samman komponenter utan att bilda cykler.
- **Sammanhängande komponenter** i en graf eller rutnät.
- **Dynamisk anslutning** och nätverk/perkolationsproblem.

## Varför det spelar roll

Union-find löser grupperings- och anslutningsproblem som annars skulle kräva upprepade O(n) grafgenomgångar, och kollapsar dem till nästan O(1) per fråga.

Det är ett nödvändigt verktyg när du måste inkrementellt slå samman mängder och testa anslutning — ett vanligt avancerat intervjuämne.