When low[v] > discovered[u]. The child’s whole branch lacks an alternate route reaching u or an earlier ancestor, so removing u–v separates it.

discovered[u] records DFS arrival order. low[u] starts there and is lowered by back edges to earlier nodes and completed child summaries. The test is strict: reaching the parent by another edge is already a backup. The iterative stack below stores a neighbor iterator for each paused call, exactly like recursive DFS, so a deep chain cannot overflow Python’s call stack. Edge IDs distinguish parallel edges from the single edge used to enter a child.

What the function promises: An undirected graph uses labels 0..n−1. Return bridge endpoint pairs in sorted order. The helper also handles disconnected graphs, self-loops, and parallel edges; the linked problem guarantees a connected simple graph.

def bridges(n, edges):
    graph = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        graph[u].append((v, edge_id))
        graph[v].append((u, edge_id))
    discovered, low = [-1] * n, [0] * n
    timer, answer = 0, []
    for start in range(n):
        if discovered[start] != -1:
            continue
        discovered[start] = low[start] = timer
        timer += 1
        stack = [(start, -1, -1, iter(graph[start]))]
        while stack:
            u, parent, incoming_edge, neighbors = stack[-1]
            try:
                v, edge_id = next(neighbors)
            except StopIteration:
                stack.pop()
                if parent != -1:
                    if low[u] > discovered[parent]:
                        answer.append(tuple(sorted((parent, u))))
                    low[parent] = min(low[parent], low[u])
                continue
            if edge_id == incoming_edge:
                continue
            if discovered[v] == -1:
                discovered[v] = low[v] = timer
                timer += 1
                stack.append((v, u, edge_id, iter(graph[v])))
            else:
                low[u] = min(low[u], discovered[v])
    return sorted(answer)

assert bridges(4, [(0,1), (1,2), (2,0), (1,3)]) == [(1,3)]
assert bridges(2, [(0,1), (0,1)]) == []
assert bridges(4, [(0,1), (2,3)]) == [(0,1), (2,3)]

Work and storage: DFS and graph construction use O(V+E) time and space. Sorting the B returned bridges adds O(B log(B+1)) time; remove output sorting if arbitrary order is acceptable.

When to recognize it: A child branch needs a route back to its parent or an earlier ancestor without using the parent edge.

Check before applying it: Skip the parent edge, not every edge to the parent vertex. Parallel edges can provide a backup route.

No. This asks for articulation points. A non-root DFS vertex u is an articulation point if some child v has low[v] ≥ discovered[u]; removing u also removes the return endpoint. A DFS root needs a separate test: more than one DFS child. The equality and root cases are meaningful differences.