Bridges Count
HardGraphDFSMath
Description
Given an undirected graph with n nodes (0..n-1) and an edge list, return the number of bridges (edges whose removal disconnects the graph). The graph may have parallel edges and self-loops.
Examples
Input:
n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]Output:
2Explanation:
Edges (1,3) and (3,4) are bridges; removing either disconnects the graph.
Input:
n = 4, edges = [[0,1],[1,2],[2,3]]Output:
3Explanation:
Every edge on a simple path is a bridge, so the count equals the number of edges, 3.
Input:
n = 3, edges = [[0,1],[1,2],[2,0]]Output:
0Explanation:
No edge of a simple cycle is a bridge, so the count is 0.
Constraints
- •
1 ≤ n ≤ 1000 - •
0 ≤ edges.length ≤ 5000