X'inhu union-find u fejn jintuża?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) isservi partizzjoni ta' elementi f' **settijiet disjunti** u jappoġġa żewġ operazzjonijiet pressoqu-O(1): **find** (x huwa f'liema sett?) u **union** (aqbad żewġ settijiet). Huwa eċċellenti għal mistoqsijiet ta' **konettività**.

## L-idea

Kull sett huwa siġra bi radikali rappreżentattiv. B'**kkompressjoni tal-mogħdija** u **unjoni bi rank/daqs**, l-operazzjonijiet jimxu f'ħin **amortizzat** pressoqu-kostanti (Ackermann inversa, α(n)).

## Eżempju

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

## Kumplessità

- **find / union:** O(α(n)) ≈ O(1) amortizzat. **Spazju:** O(n).

## Applikazzjonijiet

- **MST ta' Kruskal** — detezzjoni ta' ċiklu waqt li zżid ittafi.
- **Komponenti maqgħuda** / konettività dinamika.
- **Detezzjoni ta' ċiklu** f'graffi mhux direttiżati.
- **Perkolazzjoni**, segmentazzjoni ta' immagini, fużjoni ta' kontijiet/netwerks.

## Trappoli

Bla kkompressjoni tal-mogħdija u unjoni bi rank/daqs, is-siġar jitdegradaw għal ktiniet O(n). Ma jappoġġax **qsim** effiċjenti ta' settijiet.

## Għaliex hija importanti

Union-find twiegħed il-mistoqsija "dawn il-ħaġjiet tnejn huma maqgħuda?" f'skala ħonoża b'spiża pressoqu waħda.

Hu l-magna ġewwa Kruskal's MST u ħafna algoritmi ta' graff u clustering.

L-iż-żewġ ottimizzazzjonijiet tagħha huma lezzjoni memorabbli dwar kif il-tricks strutturali ċkejkna jipproduċu perforanza bqas-ħin pressoqu-kostanti.