Union-Find (Disjoint Set Union)

المشكلة: هل عنصران بنفس المجموعة؟

تخيّل شبكة أصدقاء تتوسّع باستمرار: كل مرة يتصادق شخصان جديدان، تدمج دائرتيهما. السؤال المتكرر: "هل شخصان معيّنان بنفس دائرة الأصدقاء (مباشرة أو عبر وسطاء)؟". Union-Find (يُعرف أيضًا Disjoint Set Union أو DSU) هيكل بيانات مصمّم بالضبط لهذا: تتبّع مجموعات لا تتقاطع، مع عمليتين سريعتين جدًا: دمج مجموعتين وفحص هل عنصران بنفس المجموعة.

الفكرة: كل مجموعة شجرة، وممثّلها الجذر

كل عنصر يشير لـ"أب" — الجذر (العنصر الذي يشير لنفسه) هو ممثّل المجموعة. عنصران بنفس المجموعة إذا وفقط إذا وصلا لنفس الجذر.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # كل عنصر أبٌ لنفسه مبدئيًا
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # تسطيح المسار
        return self.parent[x]

    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False  # بالفعل بنفس المجموعة
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        return True

تسطيح المسار (Path Compression)

بدون تحسين، find قد تمرّ بسلسلة طويلة من الآباء (شجرة "منحرفة" لقائمة). تسطيح المسار يجعل كل عنصر زُرته أثناء find يشير مباشرة للجذر — فالاستدعاء التالي لنفس العنصر يكون فوريًا تقريبًا.

الاتحاد بالرتبة (Union by Rank)

عند الدمج، نُلحق الشجرة الأقصر بجذر الشجرة الأطول (وليس العكس عشوائيًا) — هذا يمنع نمو ارتفاع الشجرة بلا داعٍ.

التعقيد: شبه ثابت عمليًا

بدمج التحسينين معًا (تسطيح المسار + الاتحاد بالرتبة)، كل عملية find أو union تعمل بتعقيد O(α(n)) تقريبًا، حيث α هي دالة أكرمان العكسية — دالة تنمو ببطء شديد لدرجة أن قيمتها لا تتجاوز 4 عمليًا لأي حجم بيانات واقعي. لأغراض عملية، اعتبرها زمنًا شبه ثابت.

أشهر تطبيقاتها

• كشف الدورات في رسم بياني غير موجّه أثناء إضافة أضلاع واحدًا تلو الآخر.
• خوارزمية Kruskal لإيجاد الشجرة الممتدة الصغرى (الدرس القادم).
• مكوّنات الاتصال (Connected Components): هل الشبكة كلّها متصلة، أم فيها جزر منفصلة؟
• أنظمة الشبكات الاجتماعية: تجميع المستخدمين بمجتمعات مترابطة بسرعة.

أخطاء شائعة

• نسيان تسطيح المسار — يجعل find تتدهور لـ O(n) بأسوأ حالة مع بيانات كبيرة، ويفقد الهيكل ميزته الأساسية.
• الظن أن Union-Find تخزّن "من هو صديق من" بالتفصيل — هي تجيب فقط "هل بنفس المجموعة؟"، لا تحتفظ بتفاصيل العلاقات الفردية.
• استخدامها لمسألة تحتاج حذف عنصر من مجموعة — Union-Find مصمّمة للدمج فقط، لا تدعم الفصل (split) بكفاءة.

🎯 التالي: الشجرة الممتدة الصغرى (MST) — خوارزمية Kruskal تستخدم Union-Find مباشرة.