Bridges Count

Problem

Count the bridges of an undirected graph with n nodes: edges whose removal increases the number of connected components.

Use a DFS with discovery times and low-link values; a tree edge u -> v is a bridge when low[v] > disc[u]. edges is a list of [u, v] pairs.

Hint

Track edge ids so the DFS does not walk back along its own edge.

case 1

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

expected: 2

case 2

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

expected: 0

case 3

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

expected: 0

case 4

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

expected: 2

case 5

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

expected: 1

Starter codePython

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

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