Quy trình lập trình · Cạnh cầu của đồ thị vô hướng

def bridge_edges(n, edges):
    if type(n) is not int or not 0 <= n <= 32:
        raise ValueError("vertex count")
    if type(edges) is not list or len(edges) > 496:
        raise ValueError("edge count")
    graph = [set() for _ in range(n)]
    for edge in edges:
        if type(edge) is not tuple or len(edge) != 2 or any(
            type(x) is not int or not 0 <= x < n for x in edge):
            raise ValueError("edge endpoints")
        a, b = edge
        if a == b or b in graph[a]:
            raise ValueError("simple undirected edges")
        graph[a].add(b); graph[b].add(a)
    timer, found = 0, []
    entered, low = [-1] * n, [0] * n
    def visit(v, parent):
        nonlocal timer
        entered[v] = low[v] = timer; timer += 1
        for u in sorted(graph[v]):
            if u == parent:
                continue
            if entered[u] < 0:
                visit(u, v); low[v] = min(low[v], low[u])
                if low[u] > entered[v]:
                    found.append(tuple(sorted((v, u))))
            else:
                low[v] = min(low[v], entered[u])
    for v in range(n):
        if entered[v] < 0:
            visit(v, -1)
    return sorted(found)