1104. Find All Bridges Using Tarjan's Algorithm

Given an undirected graph with n nodes and edges, return the number of bridges — edges whose removal increases the number of connected components — using Tarjan's bridge-finding algorithm. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the number of bridges.

Examples

Input: {"n":5,"edges":[[0,1],[1,2],[2,0],[1,3],[3,4]]}
Output: 2
Explanation: Edges 1-3 and 3-4 are bridges.

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: 0
Explanation: A cycle has no bridge.

Input: {"n":4,"edges":[[0,1],[1,2],[2,3]]}
Output: 3
Explanation: Every chain edge is a bridge.

Constraints

• 1<=n<=10^5
• undirected

Asked by