Night closures
The road service is drawing up a schedule of night repairs: each night one street is closed entirely, and it is reopened in the morning. Before the schedule is published it must be known whom each closure cuts off: how many crossroads lose their link with the rest of the world for that night, so that they cannot be reached either from the city or from beyond it.
Crossroads are numbered from 1 to n, and crossroads 1 is special: it is the whole world beyond the edge of the map, connected to every street that leaves the map. Streets are two-way. There may be several different streets between two crossroads, for example the two carriageways of one avenue. The fifth test is the streets of Almaty from the article, from the centre to the mountains: 11,724 vertices including the world and 15,169 pieces of street, and each of them in turn is proposed for closure.
Input
The first line holds n and m (2 ≤ n ≤ 100,000, 1 ≤ m ≤ 200,000). Then m lines a b, a street between crossroads a and b (a ≠ b); streets are numbered from 1 in input order. Every crossroads can be reached from crossroads 1 along the streets. Then the number of nights q (1 ≤ q ≤ 200,000) and q numbers of streets to close; numbers may repeat.
Output
q numbers, one per line: how many crossroads other than crossroads 1 will not be connected to crossroads 1 while this street is closed (the other streets are open).
Examples
Example 1
8 10 1 2 1 3 2 3 3 4 4 5 4 5 5 6 6 7 7 5 6 8 5 4 5 6 8 10
5 0 0 0 1
Example 2
4 3 1 2 2 3 2 4 3 1 2 3
3 1 1
Limits
- Time · Python
- 5000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A closure cuts anyone off only if the street is a bridge. How to find all bridges at once is told in the article. What remains is to find out whom exactly each bridge cuts off.
2Hint 2
Start the depth-first search from crossroads 1. A bridge is an edge of the search tree, and its side without crossroads 1 is the subtree of its lower end. How many vertices does it have?
3Hint 3
Look at the first sample: there are two streets between crossroads 4 and 5. What will your code do with street 5?
4The idea
One bridge search from vertex 1, and along the way the size of each subtree: when the search returns from v to its parent, size(v) is already computed and is added to the parent's size. If the edge u–v turned out to be a bridge, exactly the subtree of v is cut off: all edges from it to the outside other than the bridge would lead to ancestors, and there are none. The answer for a bridge is size(v), for any other street 0. All answers are ready before the first question, and each question costs O(1).
5Walkthrough
The search without recursion, with its own stack: in the fifth test the search stack grows to 2453 crossroads, and in the seventh to 58,130, and recursion in Python would hit its limit. For each vertex keep tin, low, size and the number of the edge it was entered by. Going back along the edge to the parent is skipped only by edge number: a second street to the same crossroads is a real detour and must lower low. On return from v to u: low(u) = min(low(u), low(v)), size(u) += size(v), and if low(v) > tin(u), record cut_off[edge] = size(v).
Why the root is crossroads 1 in particular: then the “cut-off side” of a bridge is always a subtree, and there is no need to guess which of the two parts lost its link with the world. If the search started from another vertex, a bridge above the root would need the complement: n − size.
In the city of the fifth test there are 3005 non-zero answers, as many as bridges, and 2201 of them equal one: behind the street is a single dead-end crossroads. The largest answer is 128: the roads into the mountains from the article.
5+Solution
6Complexity
O(n + m) for the search and O(1) per question; memory O(n + m). Trying “close and traverse the graph” would cost O(q(n + m)), more than twenty billion steps for the last test.
7Common mistakes
- Skipping the parent by vertex. The code “do not go back where you came from” throws out, together with the tree edge, the second street to the same crossroads. A double street becomes a bridge, and in the first sample street 5 “cuts off” four crossroads instead of none. In the city of the fifth test this produces 25 false bridges.
- Recursion. The search depth in the seventh test is 58,130; a recursive version crashes with
RecursionError, and with a raised limit it may crash the interpreter itself. - The wrong side of the bridge. If the search does not start from vertex 1, the subtree may be exactly the part that stayed with the world.
Algorithms behind it
O(V + E)
2 problems
GRA
Algorithm
Depth-first search
Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E).
O(V + E)
2 problems