ما هي بنية disjoint-set (union-find) مع path compression و union by rank؟

Question

Accepted Answer

بنية **disjoint-set** (union-find) تتتبع العناصر المقسمة إلى مجموعات غير متداخلة وتجيب على **"هل هذان العنصران في نفس المجموعة؟"** و **"دمج مجموعتين"** في **وقت قريب من الثابت**. مع **path compression** و **union by rank**، كلا العمليتين تعمل في **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
```

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

| العملية | الوقت (مع كلا التحسينات) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## الاستخدامات الشائعة

- **Kruskal's MST** — دمج المكونات دون تكوين دورات.
- **المكونات المتصلة** في رسم بياني أو شبكة.
- **الاتصالية الديناميكية** ومشاكل الشبكة/التسرب.

## لماذا يهم

Union-find يحل مشاكل التجميع والاتصال التي قد تتطلب عمليات O(n) متكررة لخطأ الرسم البياني، حيث يقللها إلى O(1) تقريباً لكل استعلام.

إنها أداة موثوقة عندما يجب عليك دمج المجموعات بشكل تدريجي واختبار الاتصال — موضوع متكرر في المقابلات على مستوى عالٍ.