Intermediate Level
Implement the minimumReorderRoutesToCapital method that returns the minimum road directions to reverse so every city can reach city zero.
You are given cities cities numbered from 0 and directed roads as [from, to]. The roads form a connected tree if direction is ignored.
Return the minimum number of roads that must be reversed so every city can travel to city 0.
Example 1
Input
cities (int) =
6connections (int[][]) =
[[0,1],[1,3],[2,3],[4,0],[4,5]]size (int) =
5Returns (int)
3Example 2
Input
cities (int) =
3connections (int[][]) =
[[1,0],[2,0]]size (int) =
2Returns (int)
0Example 3
Input
cities (int) =
5connections (int[][]) =
[[1,0],[1,2],[3,2],[3,4]]size (int) =
4Returns (int)
2Treat each directed road as two undirected traversal options.
When moving away from city 0, if the original road direction also moves away from 0, that road must be reversed. If the original direction already points toward the current path to city 0, it is fine.
Run DFS or BFS from city 0 and count the roads that point in the wrong direction.
Pseudocode:
function minimumReorderRoutesToCapital(cities, connections, size):
build graph
for each directed edge [from, to]:
add [to, 1] to graph[from]
add [from, 0] to graph[to]
visited = array filled with false
answer = 0
queue = [0]
visited[0] = true
while queue is not empty:
city = remove front
for each [next, cost] in graph[city]:
if not visited[next]:
answer += cost
visited[next] = true
add next to queue
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run