Skills101
← All coding problems

Articulation Points

hardGraphs II+40 XPTime limit 2s

A road network has n cities and m two-way roads. A city is a critical city (an articulation point) if closing it — together with every road touching it — splits some of the other cities that were connected before. Find all critical cities.

Input:

  • line 1: n m
  • next m lines: a road u v

Output: the critical cities in increasing order on one line, or -1 if there are none.

Constraints: 1 ≤ n ≤ 3·10⁴, 0 ≤ m ≤ 6·10⁴, u ≠ v, no road is listed twice. The network may be disconnected.

Think about it: use Tarjan's DFS with discovery times tin and low-links low. A non-root vertex p is critical if some DFS child v has low[v] ≥ tin[p] (that child's subtree cannot climb above p). The root of a DFS tree is critical exactly when it has two or more DFS children. One DFS, O(n + m) — prefer an iterative DFS for deep graphs.

Sample input 1

5 5
1 2
2 3
3 1
3 4
4 5

Sample output 1

3 4

Sample input 2

4 4
1 2
2 3
3 4
4 1

Sample output 2

-1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.