The missing streets
A city has n crossings and m streets, some of them one-way. Somewhere on the map there are dead-end traps: you can drive in but cannot drive out without breaking the rules. There are also places the other way round, which cannot be reached legally at all. The city hall is ready to lay a few new one-way streets, between any two crossings, anywhere, so that every crossing can reach every other. What is the smallest number of streets needed?
Input
The first line holds n and m (1 ≤ n ≤ 60,000, 0 ≤ m ≤ 100,000). Then m lines a b t: a street between crossings a and b; with t = 1 it can be driven only from a to b, with t = 0 in both directions. Loops and repeated streets occur.
Output
The smallest number of new one-way streets.
Tests five, six and seven are central Almaty from OpenStreetMap data, as in the article: the streets as mapped, the two-way streets made one-way at random, and directions by Robbins. A vertex that is not on the map stands for the whole world beyond its edge.
Examples
Example 1
8 11 1 2 1 2 3 1 3 1 1 2 4 1 4 5 1 5 6 1 6 4 1 5 7 1 7 8 1 8 7 1 3 8 1
1
Example 2
5 2 1 2 0 3 4 0
3
Limits
- Time · Python
- 6000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 12 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
Inside a strongly connected component no new streets are needed: everything there already reaches everything. Shrink each component to a point. What graph do you get?
2Hint 2
The shrunken graph has no cycles. Look at the components no arrow enters and those no arrow leaves. How many new streets are needed at least for them?
3The idea
Find the strongly connected components and look at the graph of components, the condensation. It is acyclic. Let it have s sources (components with no incoming arrows) and t sinks (with no outgoing ones); a component with no arrows at all counts as both. If there is one component, the answer is 0. Otherwise the answer is max(s, t).
Fewer is impossible: at least one new street must enter each source, otherwise it still cannot be reached, and a new street enters only one component. So there are at least s new streets, and for the same reason at least t. That max(s, t) is always enough was proved by Kapali Eswaran and Robert Tarjan in 1976. The idea is to choose as many pairs “a source and a sink reachable from it” as possible and link the pairs into one circle, drawing a street from each pair’s sink to the next pair’s source. The remaining sources and sinks are hooked onto this circle one at a time. Choosing the pairs carefully is not as simple as it seems: in 2005 S. Raghavan found an error in the published construction algorithm, although the formula itself is correct.
4Walkthrough
Find the component number of each crossing with Tarjan. Then go through all the streets: a street between different components gives the first an exit and the second an entry. Count the components without entries and without exits and print the larger count; if there is one component, zero.
Two-way streets are simply two edges. In the first example the components are {1 2 3}, {4 5 6} and {7 8}: a source, a middle and a sink, so one street suffices, from the sink to the source. In the second example there are three islands with no arrows between them, each both a source and a sink: three streets are needed, the circle 1 → 3 → 5 → 1.
On the real map of Almaty the answer is 5: that is how many trap sinks lie outside the main component, while there are only two sources. If all two-way streets are made one-way at random, 1266 new streets are needed, and by Robbins none.
4+Solution
5Complexity
Tarjan and the counting are O(n + m). A recursive depth-first search on the eleventh test goes 60,000 deep: in Python without a raised recursion limit it will crash, so the reference solution traverses the graph with its own stack of frames.
6Common mistakes
- Counting crossings instead of components. A crossing with no incoming streets is a source, but a source can be large: in the first example every crossing has both an entry and an exit, yet the answer is 1.
- Adding sources and sinks. One street from a sink to a source closes both at once.
- Forgetting that the graph may already be strongly connected. Then there is one source and one sink, the single component itself, and the answer is 0.
- Forgetting islands with no streets. A component with no arrows is a source and a sink at the same time.