Street closures
A city is preparing for road repairs: streets will be closed one after another and not reopened until the end of the repairs. A dispatcher needs to know in advance what the city will become after each closure: how many parts it will fall apart into, counting as connected the crossings between which one can drive along open streets.
Two tests are the real street graph of central Almaty from OpenStreetMap: 7909 crossings and 10,423 pieces of street. In one all streets are closed in random order, in the other only pieces of major roads.
Input
The first line holds n and m (1 ≤ n ≤ 100,000, 1 ≤ m ≤ 100,000), the number of crossings and streets. Then m lines: the ends of a street a and b (1 ≤ a, b ≤ n). Streets are numbered from 1 in input order; there can be several streets between two crossings, and a street can start and end at the same crossing. Then the number of closures q (1 ≤ q ≤ m) and q distinct street numbers in order of closure.
Output
q numbers, one per line: how many parts the city has fallen apart into right after each closure. A single crossing that no open street leads to is also a part.
Examples
Example 1
6 7 1 2 2 3 3 4 4 5 5 1 3 6 1 3 5 7 1 3 6 4
1 1 2 3 4
Example 2
4 5 1 2 1 2 2 3 3 3 3 4 4 1 4 2 5
1 1 2 3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 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
After each closure the parts can be recounted with a breadth-first search. What does that cost with a hundred thousand closures?
2Hint 2
A disjoint set union can merge parts but not cut them. All the closures are known in advance. What if you look at the repairs from the end?
3The idea
Read the list of closures backwards: it is a list of openings. Start with the city in which everything that will be closed is closed: assemble the parts from the streets that are never closed. The answer for the last closure is the number of parts now. Open the street of the last closure, and you get the city after the second-to-last one, and so on to the first. Each opening is a merge, and disjoint set union does merges almost instantly.
4Walkthrough
The parts counter starts at n and decreases by one with each successful merge. First merge the ends of all streets not in the list of closures. Then go through the list from the end: record the current number of parts as the answer for the i-th closure and only after that open the i-th street. The order matters: the answer for closure i is the city where this street is already closed. At the end print the answers in forward order.
Multiple streets and loop streets do not trouble the solution: if the ends are already in one part, the merge does nothing. In the second sample, after the first closure crossings 1 and 2 are connected by the second street, and the city is still whole.
This technique, answering queries not in the order they were asked, is called offline processing. It works because all the queries are known in advance. If closures arrived one at a time and had to be answered at once, one would need structures of dynamic connectivity, which are far more complex.
4+Solution
5Complexity
O((n + m) α(n)) time and O(n + m) memory. A traversal after each closure is O(q·(n + m)): on the real Almaty that is ten thousand traversals of the city, and in the fifth test a hundred thousand traversals of a graph of fifty thousand vertices.
6Common mistakes
- A traversal after each closure. Correct, but already in the third test, 10,423 traversals of the city, each over 7909 crossings and all their streets, it does not fit in the time.
- Recording the answer after opening. Then the answers shift by one closure: for the last one you get the city where its street is still open.
- Forgetting the streets that are never closed. In the fourth test only 2616 pieces of major roads are closed, and the remaining almost eight thousand streets are open all the time.