વિচ્છેદિત-સમૂહ (union-find) માળખું પાથ કમ્પ્રેશન અને યુનિયન બાય રેન્ક સાથે શું છે?

Question

IT Interview Practice · Accepted Answer

એક **વિચ્છેદિત-સમૂહ** (union-find) તત્વોને બિન-ઓવરલેપિંગ જૂથોમાં વિભાજિત કરે છે અને "**શું આ બે જૂથમાં છે?**" અને "**બે જૂથો એકીકૃત કરો**" ને **નજીક-સ્થિર સમયમાં** સંબોધિત કરે છે. **પાથ કમ્પ્રેશન** અને **રેન્ક દ્વારા યુનિયન** સાથે, બંને ક્રિયાકલાપ **O(α(n))** માં ચાલે છે — અસરથી O(1) (α વ્યસ્ત Ackermann ફંક્શન છે).

## તે કેવી રીતે કાર્ય કરે છે

પ્રત્યેક સમૂહ એક વૃક્ષ છે; **મૂળ** સમૂહના પ્રતિનિધિ છે. `find` મૂળ સુધી ચાલે છે; `union` એક મૂળને બીજા હેઠળ જોડે છે.

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

## કોડ

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

| ક્રિયાકલાપ | સમય (બંને ઑપ્ટિમાઇজેશન સાથે) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## સામાન્ય ઉપયોગો

- **Kruskal's MST** — ચક્ર બનાવ્યા વિના ઘટકોને એકીકૃત કરો.
- **જુદા પડતા ઘટકો** આલેખ અથવા ગ્રીડમાં.
- **ગતિશીલ જોડાણ** અને નેટવર્ક/પરક્ચુરેશન સમસ્યાઓ.

## શા માટે તે મહત્વપૂર્ણ છે

Union-find સમૂહીકરણ અને જોડાણ સમસ્યાઓ હલ કરે છે જે અન્યથા O(n) ગ્રાફ ટ્રાવર્સલ પુનરાવર્તિત કરશે, તેમને લગભગ O(1) પ્રતિ ક્વેરી સુધી ઘટાડીને.

જ્યારે પણ તમે સમૂહોને ધીમે ધીમે એકીકૃત કરવા અને જોડાણ પરીક્ષણ કરવું આવશ્યક હોય ત્યારે તે સરંજામ છે — વરિષ્ઠ-સ્તરનો સાક્ષાત્કાર વિષય.

તે કેવી રીતે કાર્ય કરે છે

કોડ

સામાન્ય ઉપયોગો

શા માટે તે મહત્વપૂર્ણ છે

સંબંધિત પ્રશ્નો