Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
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) = 6
connections (int[][]) = [[0,1],[1,3],[2,3],[4,0],[4,5]]
size (int) = 5
Return:
(int) 3
Example 2
Input:
cities (int) = 3
connections (int[][]) = [[1,0],[2,0]]
size (int) = 2
Return:
(int) 0
Example 3
Input:
cities (int) = 5
connections (int[][]) = [[1,0],[1,2],[3,2],[3,4]]
size (int) = 4
Return:
(int) 2

Treat 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 answer
Run your code to see the result.