不逐条删边，怎样一次找出所有关键边？两条平行边会改变什么

"""Static bridges of an undirected multigraph, with edge-ID semantics."""
from collections import deque
from itertools import combinations, product
import json


def checked_graph(n, edges):
    if type(n) is not int or not 0 <= n <= 128:
        raise ValueError("n must be an integer in 0..128")
    if not isinstance(edges, (list, tuple)) or len(edges) > 512:
        raise ValueError("edges must be a list/tuple of at most 512 pairs")
    result = []
    for edge in edges:
        if not isinstance(edge, (list, tuple)) or len(edge) != 2:
            raise ValueError("each edge must contain two endpoints")
        u, v = edge
        if any(type(x) is not int or not 0 <= x < n for x in (u, v)):
            raise ValueError("endpoint outside graph")
        result.append((u, v))
    return result


def find_bridges(n, edges):
    edges = checked_graph(n, edges)
    adjacency = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        adjacency[u].append((v, edge_id))
        adjacency[v].append((u, edge_id))
    tin, low = [-1] * n, [-1] * n
    bridge_flags = [False] * len(edges)
    tree_checks = []
    timer = 0

    def dfs(u, incoming_edge):
        nonlocal timer
        tin[u] = low[u] = timer
        timer += 1
        for v, edge_id in adjacency[u]:
            if edge_id == incoming_edge:
                continue
            if tin[v] != -1:
                low[u] = min(low[u], tin[v])
            else:
                dfs(v, edge_id)
                low[u] = min(low[u], low[v])
                bridge_flags[edge_id] = low[v] > tin[u]
                tree_checks.append({"edge_id": edge_id, "parent": u,
                                    "child": v, "tin_parent": tin[u],
                                    "low_child": low[v],
                                    "bridge": bridge_flags[edge_id]})

    roots = []
    for root in range(n):
        if tin[root] == -1:
            roots.append(root)
            dfs(root, -1)
    # Scanning flags keeps original edge-ID order without an extra sorting cost.
    return {"bridge_ids": [i for i, yes in enumerate(bridge_flags) if yes],
            "tin": tin, "low": low, "roots": roots, "tree_checks": tree_checks}


def bad_parent_vertex_version(n, edges):
    """Deliberate bug: skips every edge to the parent vertex."""
    edges = checked_graph(n, edges)
    adjacency = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        adjacency[u].append((v, edge_id))
        adjacency[v].append((u, edge_id))
    tin, low = [-1] * n, [-1] * n
    flags = [False] * len(edges)
    timer = 0

    def dfs(u, parent):
        nonlocal timer
        tin[u] = low[u] = timer
        timer += 1
        for v, edge_id in adjacency[u]:
            if v == parent:  # WRONG for parallel edges.
                continue
            if tin[v] != -1:
                low[u] = min(low[u], tin[v])
            else:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                flags[edge_id] = low[v] > tin[u]

    for root in range(n):
        if tin[root] == -1:
            dfs(root, -1)
    return [i for i, yes in enumerate(flags) if yes]


def component_count(n, edges, skipped_id=None):
    # Independent oracle: rebuild actual remaining roads, then count BFS groups.
    adjacency = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        if edge_id != skipped_id:
            adjacency[u].append(v)
            adjacency[v].append(u)
    seen = set()
    count = 0
    for start in range(n):
        if start in seen:
            continue
        count += 1
        seen.add(start)
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in adjacency[u]:
                if v not in seen:
                    seen.add(v)
                    queue.append(v)
    return count


def deletion_oracle(n, edges):
    if n > 5 or len(edges) > 24:
        raise ValueError("deletion oracle limited to five vertices and 24 edges")
    before = component_count(n, edges)
    after = [component_count(n, edges, i) for i in range(len(edges))]
    return [i for i, count in enumerate(after) if count > before], before, after


def main():
    checks = 0
    graphs = 0
    deletions = 0

    def check(condition):
        nonlocal checks
        if not condition:
            raise AssertionError("bridge verification failed")
        checks += 1

    for n in range(5):
        pairs = list(combinations(range(n), 2))
        for multiplicities in product((0, 1, 2), repeat=len(pairs)):
            nonloops = [edge for edge, count in zip(pairs, multiplicities)
                        for _ in range(count)]
            for loops in product((0, 1), repeat=n):
                edges = nonloops + [(v, v) for v, yes in enumerate(loops) if yes]
                result = find_bridges(n, edges)
                wanted, before, after = deletion_oracle(n, edges)
                check(result["bridge_ids"] == wanted)
                check(sorted(result["tin"]) == list(range(n)))
                check(all(0 <= low <= tin for low, tin in zip(result["low"], result["tin"])))
                check(len(result["roots"]) == before)
                graphs += 1
                deletions += len(after)

    parallel_edges = [(0, 1), (0, 1), (1, 2)]
    parallel = find_bridges(3, parallel_edges)
    bad = bad_parent_vertex_version(3, parallel_edges)
    check(parallel["bridge_ids"] == [2])
    check(bad == [0, 2])
    check(parallel["low"] == [0, 0, 2])
    disconnected_edges = [(0, 1), (1, 2), (2, 0), (3, 4), (4, 4)]
    disconnected = find_bridges(6, disconnected_edges)
    check(disconnected["bridge_ids"] == [3])
    check(len(disconnected["roots"]) == 3)
    path = [(i, i + 1) for i in range(127)]
    check(find_bridges(128, path)["bridge_ids"] == list(range(127)))
    check(find_bridges(1, [(0, 0)] * 512)["bridge_ids"] == [])

    invalid = [(True, []), (-1, []), (129, []), (2.0, []), (2, None),
               (2, [(0, 2)]), (2, [(False, 1)]), (2, [(0, 1.0)]),
               (2, [(0,)]), (2, ["01"]), (0, [(0, 0)]),
               (1, [(0, 0)] * 513)]
    for args in invalid:
        try:
            find_bridges(*args)
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid graph accepted")

    report = {"checks_passed": checks, "exhaustive_multigraphs": graphs,
              "oracle_single_edge_deletions": deletions,
              "parallel_example": {"edges": parallel_edges, **parallel,
                                   "bad_parent_vertex_ids": bad},
              "disconnected_bridge_ids": disconnected["bridge_ids"],
              "disconnected_roots": disconnected["roots"],
              "maximum_path_vertices_checked": 128,
              "invalid_inputs_rejected": len(invalid),
              "scope": "static undirected graph; delete one edge ID at a time; no dynamic maintenance"}
    print(json.dumps(report, indent=2))


if __name__ == "__main__":
    main()