Unioni-find ni nini na inatumika wapi?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) inafuatilia mgawanyiko wa vipengele katika **seti ambazo hazinaingiliana** na inasaidia operesheni mbili karibu O(1): **find** (x iko seti ipi?) na **union** (unganisha seti mbili). Ni bora sana kwa maswali ya **uwezekano wa kuunganishwa**.

## Wazo

Kila seti ni mti wenye wakilishi mzizi. Na **path compression** na **union by rank/size**, operesheni hutumia wakati **amortized** karibu mara kwa mara (inverse Ackermann, α(n)).

## Mfano

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

## Utata wa Mahesabu

- **find / union:** O(α(n)) ≈ O(1) amortized. **Nafasi:** O(n).

## Matumizi

- **Kruskals MST** — kugundua mizunguko wakati wa kuongeza kingo.
- **Vijenzi vilivyounganishwa** / uunganaji wenye nguvu.
- **Kugundua mizunguko** katika grafu zisizo na mwelekeo.
- **Uhamiaji**, ugawaji wa picha, kuunganisha akaunti/mitandao.

## Tosheka

Bila path compression na union by rank, miti inabadilika kuwa mtandao wa O(n). Haisaidii *kutenganisha* seti kwa ufanisi.

## Kwa nini ni muhimu

Union-find inajibu "je, vitu hivi viwili vimeunganishwa?" kwa kiwango kikubwa na karibu hakuna gharama.

Ni injini ndani ya Kruskals MST na algoriti nyingi za grafu na kuorodhesha.

Osasizi wake mbili ni somo lililozoea jinsi hila ndogo za miundo inavyotoa utendaji karibu wa mara kwa mara.