Count Bridges in an Undirected Graph

Given an undirected graph, count how many edges are bridges. A bridge is an edge whose removal increases the number of connected components. Pattern focus: Bridges. This is the counting version of bridge detection.

Input Format

n = number of vertices, edges = undirected edges [u, v]

Output Format

number of bridges in the graph

Constraints

  • 1 <= n <= 10^5
  • 1 <= edges.length <= 2 * 10^5

Examples

Example 1:

Input:

n = 4
edges = [[1,2],[2,3],[3,1],[3,4]]

Output:

1

Explanation:

Only edge (3,4) is a bridge.

Example 2:

Input:

n = 5
edges = [[1,2],[2,3],[3,1],[3,4],[4,5]]

Output:

2

Explanation:

Edges (3,4) and (4,5) are bridges.

Example 3:

Input:

n = 4
edges = [[1,2],[2,3],[3,4]]

Output:

3

Explanation:

All three edges are bridges because the graph is a simple path.

Loading...
Count Bridges in an Undirected Graph