Menene union-find kuma ina aka yi amfani dashi?

Question

Accepted Answer

**Union-Find** (Disjoint Set Union) yana nuna rabwar abubuwa zuwa **saitosai masu garida** kuma yana goyan bayan aiki biyu kusan-O(1): **find** (x yana saita mai?) da **union** (haɗa saitosai biyu). Yana da kyau wajen ajiyar tambayoyin **haɗi**.

## Tunani

Kowane saita itace mai wakilin tushe. Tare da **path compression** da **union by rank/size**, ayyukan gudun jiya a gurin kusan jiya **amortized** lokaci (inverse Ackermann, α(n)).

## Misali

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

## Tsari

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

## Abubuwan aikace-aikace

- **Kruskal's MST** — gano kewayo yayin ƙara gefuna.
- **Sassan da aka haɗa** / haɗin aiki na yau da kullun.
- **Gano kewayo** a cikin jaduwali mara kwatantawa.
- **Percolation**, warewa hoton, haɗin kasuwa/hanyar sadarwa.

## Damuwawa

Ba tare da path compression da union by rank ba, bishiyoyi suka rasa zuwa O(n) sarari. Ba ya goyan bayan *raba* saitosai da kyau.

## Menene akamalikas

Union-Find yana amsa "an haɗa waɗannan abubuwa?" a girma maras iyaka ba tare da kusan baɗi ba.

Ita ce injin a ciki Kruskal's MST da abubuwan lissafin jirgin ruwa da tara.

Gidajen hanyoyinta biyu sune barni da kuwa a yanke karami yadda ƙananan dabugur na tsari suka bayar kusan jiya na jiya.