Bridges in a Graph
hardGraphs II+40 XPTime limit 2s
A power grid has n substations and m two-way lines. A line is critical (a bridge) if cutting it alone splits some substations that were connected before. Find all critical lines.
Input:
- line 1:
n m - next
mlines: a lineu v
Output:
- line 1: the number of bridges
k - next
klines: each bridge asa bwitha < b, sorted bya, then byb
Constraints: 1 ≤ n ≤ 3·10⁴, 0 ≤ m ≤ 6·10⁴, u ≠ v, no line is listed twice. The grid may be disconnected.
Think about it: removing each line and re-checking connectivity is O(m·(n + m)) — too slow. Tarjan's low-link DFS does it in one pass: record each node's discovery time tin[v] and low[v], the earliest time reachable from v's subtree using one back edge. A tree edge p → v is a bridge exactly when low[v] > tin[p]. Deep graphs can overflow recursion — consider an iterative DFS.
Sample input 1
5 5 1 2 2 3 3 1 3 4 4 5
Sample output 1
2 3 4 4 5
Sample input 2
4 4 1 2 2 3 3 4 4 1
Sample output 2
0
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).