Union-Find શું છે અને તેનો ઉપયોગ ક્યાં થાય છે?

Question

IT Interview Practice · Accepted Answer

**Union-Find** (Disjoint Set Union) તત્વોના વિભાજનને **અલગ સેટ્સ**માં ટ્રૅક કરે છે અને બે લગભગ-O(1) ક્રિયાઓને સમર્થન આપે છે: **find** (x કયા સેટમાં છે?) અને **union** (બે સેટ્સ મર્જ કરો). તે **કનેક્ટિવિટી** પ્રશ્નોમાં ઉત્તમ છે.

## ખ્યાલ

પ્રત્યેક સેટ એક પ્રતિનિધિ રુટ સાથે વૃક્ષ છે. **path compression** અને **union by rank/size** સાથે, ક્રિયાઓ લગભગ સ્થિર **amortized** સમયમાં ચલાય છે (inverse Ackermann, α(n)).

## ઉદાહરણ

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

## જટિલતા

- **find / union:** O(α(n)) ≈ O(1) amortized. **જગ્યા:** O(n).

## એપ્લીકેશન્સ

- **Kruskal's MST** — ધાર ઉમેરતી વખતે સાયકલ શોધ.
- **કનેક્ટેડ કમ્પોનન્ટ્સ** / ગતિશીલ કનેક્ટિવિટી.
- **સાયકલ શોધ** અનિર્દેશિત આલેખમાં.
- **Percolation**, ઇમેજ સેગમેન્ટેશન, એકાઉન્ટ/નેટવર્ક મર્જીંગ.

## ત્રુટિઓ

Path compression અને union by rank વિના, વૃક્ષો O(n) સાંકળોમાં નિમ્ન બને છે. તે સેટ્સનું કુશળ *વિભાજન* સમર્થન નથી આપે.

## તે કેમ મહત્વપૂર્ણ છે

Union-Find "શું આ બે વસ્તુઓ જોડાયેલ છે?" ને વિશાળ પ્રમાણમાં લગભગ કોઈ ખર્ચ વિના જવાબ આપે છે.

તે Kruskal's MST અને ઘણામાં આલેખ અને ક્લસ્ટરીંગ અલ્ગોરિધમમાં મોટર છે.

તેના બે ઑપ્ટિમાઇઝેશન્સ એક સ્મરણીય પાઠ છે કે કેવી રીતે નાની માળખાકીય યુક્તિઓ લગભગ-સ્થિર-સમય કામગીરી આપે છે.

ખ્યાલ

ઉદાહરણ

જટિલતા

એપ્લીકેશન્સ

ત્રુટિઓ

તે કેમ મહત્વપૂર્ણ છે

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