Graphs 0/61

Lesson 7 of 7 Advanced

Bridges and articulation points

Find bridges and cut vertices from DFS low values, orient a bridgeless graph one way, and find strongly connected components with Tarjan’s algorithm.

5,076 words · 23 min read

Part 1 of 11 Bridges

Bridges

Graph searches find routes and shortest paths, and they can also find the edges a graph cannot do without. An edge of an undirected graph is a bridge when removing it leaves two vertices that were joined with no path between them. An edge on a cycle is not a bridge, because the rest of the cycle is a second route between its ends. If an edge lies on no cycle, it is a bridge, since any other route between its ends would close a cycle with it. CSES's Necessary Roads asks for every bridge of a connected graph.

A country has nn cities and mm two-way roads, and every city can reach every other. A road is necessary if, once it is removed, some two cities can no longer reach each other. Find every necessary road.

The first input line holds nn and mm. Each of the next mm lines holds two cities aa and bb joined by a road. No two roads join the same pair of cities, and no road joins a city to itself. Print the number of necessary roads kk, then the kk roads, in any order.

Constraints

  • 2≤n≤1052 \le n \le 10^5
  • 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5
  • 1≤a,b≤n1 \le a, b \le n

Sample · Input

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

Output

2
3 5
4 5

In the sample, cities 1, 2 and 4 form a triangle, and a tail runs from city 4 to city 5 to city 3. Each road of the triangle has a way around it through the third city, so none of them is necessary. The road from 4 to 5 is the only link between the triangle and cities 3 and 5, and the road from 3 to 5 is the only link to city 3. Those two roads are the answer.

The direct method tests each road: remove it, search to see whether the graph is still connected, and put it back. Each search costs O(n+m)O(n + m), and there is one search per road, so at the limits the work is

m×(n+m)=2×105×3×105=6×1010 steps.\begin{aligned} m \times (n + m) &= 2 \times 10^5 \times 3 \times 10^5 \\ &= 6 \times 10^{10} \text{ steps.} \end{aligned}

At a rough 10810^8 steps a second that is 600 seconds, and the time limit is one second.