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
mlines: a roadu 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).