1075. Make It Strongly Connected
A district has n junctions numbered 0 to n-1 and some one-way streets: edges[i] = [u, v] allows traffic from junction u to junction v. Streets may repeat and a street may start and end at the same junction.
The council wants a network in which a driver can get from every junction to every other junction. It will build extra one-way streets, each between any two junctions of its choice, and wants to build as few as possible.
Return the minimum number of streets that must be added. Return 0 if the network already has the property (this includes a district with a single junction).
Example 1
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output:
- 1
- Explanation:
One new street from junction 3 back to junction 0 closes the loop, and nothing cheaper is possible.
Example 2
- Input:
- n = 3, edges = [[0,1],[1,2],[2,0]]
- Output:
- 0
- Explanation:
The three junctions already form a cycle, so every junction can reach every other and nothing is added.
Example 3
- Input:
- n = 5, edges = [[0,1],[2,1],[2,3],[4,3]]
- Output:
- 3
- Explanation:
Junctions 0, 2 and 4 have no street leading in and junctions 1 and 3 have none leading out; each new street cures at most one of each kind, so three are needed.
Constraints
1 ≤ n ≤ 5 * 104
0 ≤ edges.length ≤ 105
edges[i].length == 2
0 ≤ edges[i][j] < n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)