One-way street fix
HardOnline Assessment
Find the fewest one-way streets a town must build so that every junction can reach every other junction.
A town has n junctions numbered 0 to n - 1 and a list of existing one-way streets. The street [a, b] can only be driven from junction a to junction b. A street may start and end at the same junction, and the same street may be listed more than once; neither changes what is reachable.
The council wants a town where, starting from any junction, a driver can reach every other junction by following streets in their allowed direction (passing through other junctions on the way is fine). To get there it may build new one-way streets between any two junctions, in whichever direction it likes. Each new street costs the same.
Input:
n: the number of junctions.streets: a list of[a, b]existing one-way streets, with0 <= a, b < n(possibly empty).
Output: an integer, the smallest number of new streets that must be built so that every junction can reach every other. If the town already works (including the case of a single junction), return 0.
Towns can have hundreds of junctions, so trying out candidate sets of new streets will not finish in time.
Example 1
- Input:
- [4,[[0,1],[1,2],[2,3]]]
- Output:
- 1
- Explanation
- The streets form a single path 0 → 1 → 2 → 3. Junction 0 cannot be reached from anywhere and junction 3 leads nowhere, but one new street from 3 back to 0 closes the loop and every junction then reaches every other. The answer is 1.
Example 2
- Input:
- [7,[[0,1],[1,0],[0,2],[3,2],[4,3],[3,4],[5,6]]]
- Output:
- 3
- Explanation
- Junctions 0 and 1 drive to each other, as do 3 and 4, so the groups are {0,1}, {2}, {3,4}, {5} and {6}. Nothing leads into {0,1}, {3,4} or {5}, and nothing leaves {2} or {6}. Each group that nothing enters needs a new street coming in and each group that leads nowhere needs one going out, and a new street can serve one of each, so the answer is the larger count, 3 (three groups with no way in versus two with no way out).
Example 3
- Input:
- [4,[[0,1],[1,2],[2,3],[3,0],[2,2],[0,1]]]
- Output:
- 0
- Explanation
- The four junctions already form the cycle 0 → 1 → 2 → 3 → 0. The self-loop at junction 2 and the repeated street 0 → 1 change nothing, so no new street is needed and the answer is 0.
Constraints
1 <= n <= 6000 <= streets.length <= 2,5000 <= a, b < nfor every street[a, b]