Union-Find (Disjoint Set Union) Union-Find (DSU)

الصياغة

parent = list(range(n))
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # تسطيح المسار
    return parent[x]
def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[rb] = ra

📄 مثال

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):
        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

uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.find(0) == uf.find(2))  # True — بنفس المجموعة
print(uf.find(0) == uf.find(3))  # False

أهم النقاط

💡 نصائح عملية

• لا تنسَ تسطيح المسار — بدونه تفقد الخوارزمية أهم ميزة أدائها وتقترب من O(n) بأسوأ حالة

⚠️ أخطاء شائعة

• الظن أن Union-Find تخزّن تفاصيل العلاقات الفردية بين العناصر — هي تجيب فقط 'هل بنفس المجموعة؟'، لا 'كيف ترتبط بالتحديد؟'

خصائص ذات صلة