Menene tsarin disjoint-set (union-find) tare da damje jiya da haɗa ta matsala?

Question

Accepted Answer

**Tsarin disjoint-set** (union-find) yana yin raini ɗin abubuwa da aka raba cikin rukunoni marasa juyawa kuma yana amsa "**shin waɗannan biyun suke cikin rukunin gida?**" da "**haɗa rukunoni biyu**" a cikin **lokacin kusan daidai**. Tare da **damje jiya** da **haɗa ta matsala**, aiki biyu sukan gudana a **O(α(n))** — tasiri O(1) (α aiki ne na juyawa Ackermann).

## Yadda yake aiki

Kowane saita itace ne; **tushen** wakilin saita ne. `find` yana tafiya zuwa tushen; `union` yana haɗa tushen daya a ƙarƙashin wani.

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

## Kodeks

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

| Aiki | Lokaci (tare da karbuwa biyu) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Gayyatawa da gida

- **MST na Kruskal** — haɗa abubuwa ba tare da samuwa lanƙwasa ba.
- **Abubuwa da alaƙa** a cikin jadawali ko grid.
- **Alaƙar ƙyam** da kadarori na sadarwa/infiltration.

## Me yasa yake mahimma

Union-find yana warware matsaloli na rukunawa da alaƙa waɗanda ba haka ba zai buƙaci juriya O(n) jadawali don ubanta, yana rufewa su zuwa kusan O(1) ga buɗe.

Kada sannu kayan aiki a kowane lokaci da dole ne ka haɗa saiti ɗin kwamfuta da gwada alaƙa — batu na jira na manyan jiya.