1019. Find All Articulation Points (Bridges Intro)

Given an undirected graph with n nodes and a list of edges, return all articulation points (cut vertices) — nodes whose removal increases the number of connected components — sorted in ascending order. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Array — the sorted articulation points.

Examples

Input: {"n":5,"edges":[[0,1],[1,2],[2,0],[1,3],[3,4]]}
Output: [1,3]
Explanation: Removing 1 or 3 disconnects the graph.

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

Input: {"n":3,"edges":[[0,1],[1,2]]}
Output: [1]
Explanation: The middle is a cut vertex.

Constraints

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

Asked by