Quy trình lập trình · Ghép cặp hai phía cực đại về số lượng

def maximum_matching(edges, right_count):
    if type(right_count) is not int or not 0 <= right_count <= 32 or type(edges) not in (list, tuple) or len(edges) > 32:
        raise ValueError("matching.size")
    if any(type(row) not in (set, frozenset) or any(type(v) is not int or not 0 <= v < right_count for v in row) for row in edges):
        raise ValueError("matching.edge")
    owners = [-1] * right_count
    def augment(left, seen):
        for right in sorted(edges[left]):
            if right in seen:
                continue
            seen.add(right)
            if owners[right] == -1 or augment(owners[right], seen):
                owners[right] = left
                return True
        return False
    for left in range(len(edges)):
        augment(left, set())
    return sorted((left, right) for right, left in enumerate(owners) if left != -1)