A crossing under repair
A crossroads is closed entirely for repairs: you can neither drive through it nor turn there, but all other crossroads and streets are open. If the crossroads was the only link between parts of the city, people in different parts lose each other. For each crossroads, count how many pairs of other crossroads lose their connection if it is closed.
Streets are two-way, and there may be several streets between two crossroads. The fifth test is the streets of Almaty from the article, from the centre to the mountains; there crossroads 1 is the whole world beyond the edge of the map, and an answer is needed for it too.
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). Every crossroads can be reached from every other.
Output
n numbers, one per line: for each crossroads v, the number of unordered pairs {x, y} of distinct crossroads other than v with no path between them while v is closed.
Examples
Example 1
7 8 1 2 2 3 3 1 3 4 4 5 5 6 6 4 4 7
0 0 8 11 0 0 0
Example 2
4 3 1 2 2 3 3 4
0 2 2 0
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
The answer is non-zero only for articulation points. When a point v is closed, the rest of the city falls apart into several parts. If their sizes are known, the number of lost pairs is one formula.
2Hint 2
What parts does the city without v consist of? Think about the depth-first search tree: which subtrees of v's children fall off whole, and which stay connected to what is above v?
3Hint 3
In the first sample close crossroads 4. The triangle 4, 5, 6 touches crossroads 4 by the edge 6–4. Does it fall off or not?
4The idea
A depth-first search, as in the article, plus subtree sizes. A child c of a vertex v falls off together with its whole subtree if low(c) ≥ tin(v): from the subtree you cannot climb above v. Such subtrees are separate parts, with no edges between them: by the lemma in the article all non-tree edges lead to ancestors. The other children hold on to the upper part of the city and form one more part with it, of size n − 1 − Σ of those that fell off. At the root all children fall off. If the parts have sizes s1, …, sk with sum T = n − 1, the pairs in different parts number
$$\frac{T^2 - \sum_i s_i^2}{2}.$$5Walkthrough
The search without recursion, with a stack of frames. On return from c to v: update low(v), add size(c) to size(v), and if v is the root or low(c) ≥ tin(v), add size(c) to the sum of v's fallen-off parts and size(c)² to the sum of their squares. After the search, for each vertex the remainder rest = n − 1 − sum, and the answer is (T² − sum of squares − rest²) / 2. For a vertex that is not an articulation point there is one part, rest = T, and the answer is zero by itself.
In the first sample crossroads 4 has three parts: {1, 2, 3}, {5, 6} and {7}. The pairs number 3·2 + 3·1 + 2·1 = 11. The part {5, 6} touches crossroads 4 by the edge 6–4, so low(5) = tin(4), and it falls off by the non-strict inequality.
In the city of the fifth test there are 2553 non-zero answers: 2552 articulation points and the world beyond the edge of the map itself, which, if closed, separates pieces of the city connected only by streets beyond the edge. The most pairs, 1,484,160, are lost at two crossroads, at the start of the road to Medeu and at the start of the road into the Big Almaty Gorge: each divides the graph into 128 vertices in the mountains and 11,595 others, and 128 · 11,595 = 1,484,160.
5+Solution
6Complexity
O(n + m): one search and one pass over the vertices. The answer reaches n²/2 ≈ 5·10⁹: in Go int is 64-bit, in Python numbers are unbounded, but in languages with a 32-bit int it will overflow.
7Common mistakes
- A strict inequality. The bridge test low(c) > tin(v) instead of the vertex test low(c) ≥ tin(v). A part that touches v itself by a back edge is counted as connected to the rest of the city, although without v it falls off. In the first sample crossroads 4 gets 5 instead of 11.
- The root by the general rule. At the root the condition low(c) ≥ tin(root) holds for every child, and that is right: all of the root's children fall off. The mistake is to check “more than one child” and stop there: the number of pairs depends on the sizes of all parts.
- Brute force. Closing each crossroads and counting the parts by a traversal is O(n(n + m)), billions of steps in the last test.
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