Skills101
← All coding problems

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 m lines: a line u v

Output:

  • line 1: the number of bridges k
  • next k lines: each bridge as a b with a < b, sorted by a, then by b

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).

Loading editor…

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