Bridges Sorted Edge List

Problem

List every bridge of an undirected graph as sorted [min, max] endpoints.

A bridge is an edge whose removal increases the number of connected components. DFS with discovery times and low-link values marks a tree edge u -> v as a bridge when low[v] > disc[u]; parallel edges are handled with edge ids. Return the bridge list sorted by endpoint pair.

Hint

Track the parent edge by id so a parallel edge does not masquerade as a back edge.

Test cases

case 1

in: [3,[[0,1],[1,2]]]

expected: [[0,1],[1,2]]

case 2

in: [3,[[0,1],[1,2],[2,0]]]

expected: []

case 3

in: [5,[[0,1],[1,2],[2,0],[1,3],[3,4]]]

expected: [[1,3],[3,4]]

case 4

in: [4,[[0,1],[1,2],[2,3],[3,0]]]

expected: []

case 5

in: [3,[[0,1],[0,1],[1,2]]]

expected: [[1,2]]

Starter codePython

def bridges_list(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor