Funkcje programu · Minimalne lasy rozpinające

def spanning_forest(count, edges):
    if type(count) is not int or not 0 <= count <= 64 or type(edges) is not list or len(edges) > 1024:
        raise ValueError("forest.input")
    ordered = []
    for edge in edges:
        if type(edge) not in (list, tuple) or len(edge) != 3 or any(type(x) is not int for x in edge):
            raise ValueError("forest.edge")
        a, b, weight = edge
        if not 0 <= a < count or not 0 <= b < count or abs(weight) > 10**9:
            raise ValueError("forest.bounds")
        ordered.append((weight, min(a, b), max(a, b)))
    parent = list(range(count))
    def root(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    selected, total = [], 0
    for weight, a, b in sorted(ordered):
        x, y = root(a), root(b)
        if x != y:
            parent[x] = y
            selected.append((a, b, weight))
            total += weight
    return total, selected