Nini ni muundo wa seti-tofauti (union-find) wenye kubadilisha njia na muungano kwa kiwango?

Question

IT Interview Practice · Accepted Answer

**Seti-tofauti** (union-find) inafuatilia vipengele vinavyogawanywa katika vikundi visivyolingana na kujibu "**je, hizi mbili ziko katika kundi moja?**" na "**unganisha vikundi viwili**" katika **takriban wakati wa mara kwa mara**. Kwa **kubadilisha njia** na **muungano kwa kiwango**, operesheni zote mbili zinaendelea katika **O(α(n))** — takriban O(1) (α ni kazi ya kinyume cha Ackermann).

## Jinsi inavyofanya kazi

Kila seti ni mti; **mizani** ni mjumbe wa seti. `find` huenda kwenda mizani; `union` inaunganisha mizani moja chini ya nyingine.

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

## Msimbo

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

| Operesheni | Wakati (kwa maboresho yote mawili) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Matumizi ya kawaida

- **MST ya Kruskal** — unganisha sehemu bila kuunda mizunguko.
- **Sehemu zilizounganishwa** katika grafu au kimiani.
- **Muunganisho wa kina** na matatizo ya mtandao/kuvuja.

## Kwa nini inayanza

Union-find hutatua matatizo ya kuweka vikundi na uunganisho ambayo kwa njia nyingine itahitaji marudio ya O(n) kupitia grafu, na kuiangukia karibu O(1) kwa swali.

Ni chombo kinachohitajika wakati unapokabili kubadilisha seti na kumjaribu muunganisho — mada ya kawaida katika mahojiano ya kiwango cha juu.

Jinsi inavyofanya kazi

Msimbo

Matumizi ya kawaida

Kwa nini inayanza

Maswali yanayohusiana