Medium
Quiz
#1466 Reorder Routes to Make All Paths Lead to the City Zero
APPROACH
A network of n cities (labeled 0 to n-1) is connected as a tree with n-1 directed roads. Road connections[i] = [ai, bi] runs one-way from city ai to city bi. A major event is coming to city 0 and every other city must be able to reach it.
Determine the minimum number of roads you need to reverse so that every city has a path leading to city 0. It is guaranteed a valid solution always exists.
Example 1:
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Example 2:
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Example 3:
Input: n = 3, connections = [[1,0],[2,0]]
Output: 0
1 of 4
1:00
What is the optimal approach for this problem?