المجموعات المنفصلة وغابات الامتداد الدنيا

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, vertex):
        if not 0 <= vertex < len(self.parent):
            raise ValueError("Unknown vertex")
        while self.parent[vertex] != vertex:
            self.parent[vertex] = self.parent[self.parent[vertex]]
            vertex = self.parent[vertex]
        return vertex
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

sets = DisjointSet(4)
print(sets.union(0, 1))
print(sets.union(1, 0))
print(sets.find(0) == sets.find(1))
print(sets.find(0) == sets.find(2))

True
False
True
False

يحفظ الاتحاد المكرر التقسيم. ولا يعد رقم الممثل المحدد جزءا من العقد الخارجي.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        if not 0 <= x < len(self.parent):
            raise ValueError("Unknown vertex")
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

def kruskal(n, edges):
    if n < 0:
        raise ValueError("Vertex count must be nonnegative")
    if any(not (0 <= a < n and 0 <= b < n) for _, a, b in edges):
        raise ValueError("Unknown vertex")
    sets = DisjointSet(n)
    total, chosen, components = 0, [], n
    for weight, a, b in sorted(edges):
        if sets.union(a, b):
            total += weight
            chosen.append((a, b))
            components -= 1
    return total, chosen, components

print(kruskal(4, [(1,0,1), (4,0,2), (2,1,2), (3,2,3), (7,1,3)]))
print(kruskal(3, [(2,0,1)]))

(6, [(0, 1), (1, 2), (2, 3)], 1)
(2, [(0, 1)], 2)

يعطي الرسم الأول شجرة مجموع وزنها 6. ويحوي الرسم الثاني مكوّنين، ولذلك يعطي غابة.