ایک disjoint-set (union-find) ڈھانچہ کیا ہے جس میں path compression اور union by rank ہو؟

Question

Accepted Answer

ایک **disjoint-set** (union-find) عناصر کو غیر منقسم گروپس میں تقسیم کرتا ہے اور "**کیا یہ دونوں ایک گروپ میں ہیں؟**" اور "**دو گروپس کو ملائیں**" کے سوالات کا جواب **تقریباً مستقل وقت** میں دیتا ہے۔ **path compression** اور **union by rank** کے ساتھ، دونوں operations **O(α(n))** میں چلتے ہیں — بہ اثر O(1) (α inverse Ackermann function ہے)۔

## یہ کیسے کام کرتا ہے

ہر set ایک درخت ہے؛ **root** set کا نمائندہ ہے۔ `find` root تک چلتا ہے؛ `union` ایک root کو دوسری کے نیچے جوڑتا ہے۔

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

## Code

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

| Operation | وقت (دونوں optimizations کے ساتھ) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## عام استعمالات

- **Kruskal's MST** — components کو ملائیں بغیر cycles بنائے۔
- **Connected components** گراف یا grid میں۔
- **Dynamic connectivity** اور network/percolation مسائل۔

## یہ کیوں اہم ہے

Union-find grouping اور connectivity کے مسائل کو حل کرتا ہے جو ورنہ بار بار O(n) graph traversals کی ضرورت ہوتی، انہیں تقریباً O(1) فی query میں سمیٹتا ہے۔

یہ ایک بہترین ٹول ہے جب بھی آپ کو incremental طور پر sets کو ملانا اور connectivity کو test کرنا ہو — ایک بار بار senior-level interview topic۔