Hvad er en disjoint-set (union-find) struktur med stikomlæsning og forening efter rang?

Question

Accepted Answer

En **disjoint-set** (union-find) sporer elementer opdelt i ikke-overlappende grupper og besvarer **"er disse to i samme gruppe?"** og **"flet to grupper"** i **næsten konstant tid**. Med **stikomlæsning** og **forening efter rang** kører begge operationer i **O(α(n))** — praktisk set O(1) (α er den inverse Ackermann-funktion).

## Sådan fungerer det

Hver mængde er et træ; **roden** er mængdens repræsentant. `find` går til roden; `union` forbinder en rod under en anden.

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

| Operation | Tid (med begge optimeringer) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Almindelig brug

- **Kruskals MST** — flet komponenter uden at danne cyklusser.
- **Forbundne komponenter** i en graf eller gitter.
- **Dynamisk tilslutning** og netværks-/perkolationsproblemer.

## Hvorfor det betyder noget

Union-find løser gruppering og forbindelsesproblemer, som ellers ville kræve gentagen O(n) grafgennemgang, hvilket kollapser dem til næsten O(1) pr. forespørgsel.

Det er et standard værktøj, når du skal inkrementelt flette sæt og teste forbindelser — et hyppigt tema på seniorinterview.