1039. Critical Connections — Bridges in Graph

Given an undirected graph with n nodes and a list of edges, return all critical connections (bridges) — edges whose removal increases the number of connected components. Return each bridge as [min, max] and the whole list sorted in ascending order. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Nested array — the sorted bridges.

Examples

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

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

Input: {"n":3,"edges":[[0,1],[1,2]]}
Output: [[0,1],[1,2]]
Explanation: Both chain edges are bridges.

Constraints

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

Asked by