Vad är union-find och var används det?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) spårar en partition av element i **disjunkta mängder** och stöder två nästan-O(1)-operationer: **find** (vilken mängd tillhör x?) och **union** (slå samman två mängder). Det är utmärkt för **anslutnings**-frågor.

## Idén

Varje mängd är ett träd med en representativ rot. Med **path compression** och **union by rank/size** körs operationerna i nästan konstant **amorterad** tid (inverse Ackermann, α(n)).

## Exempel

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # compress
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## Komplexitet

- **find / union:** O(α(n)) ≈ O(1) amorterad. **Utrymme:** O(n).

## Tillämpningar

- **Kruskals MST** — cykeldetektering vid kantillägg.
- **Anslutna komponenter** / dynamisk anslutning.
- **Cykeldetektering** i oriktade grafer.
- **Perkolation**, bildöversegmentering, sammanslutning av konton/nätverk.

## Fallgropar

Utan path compression och union by rank degraderas träd till O(n)-kedjor. Det stöder inte effektiv *uppdelning* av mängder.

## Varför det spelar roll

Union-find svarar på "är dessa två saker anslutna?" i massiv skala med nästan ingen kostnad.

Det är motorn inuti Kruskals MST och många graf- och klusteralgoritmer.

Dess två optimeringar är en minnesvärdig läxa i hur små strukturella knep ger nästan konstant prestanda.