Solution: Reorder Routes to Make All Paths Lead to the City Zero

Statement

There are n cities labeled from $0$ to $n - 1$, connected by $n - 1$ roads, so there is only one route between any two cities. This road network forms a tree structure.

Last year, the Ministry of transport made all roads one-way due to their narrow width. These roads are represented as connections, where each entry connections[i] $= [a_i, b_i]$ means there is a road going from city $a_i$ to city $b_i$​.

This year, a major event will occur in the capital city (city $0$), and people from all other cities must reach it. Your task is to reorient some roads so every city has a valid path leading to city $0$. Return the minimum number of roads that must be changed to achieve this.

Note: A solution is guaranteed to exist, meaning that every city can eventually reach city $0$ after reordering.

Constraints:

• $2 \leq$ n $\leq 5 * 10^4$

• connections.length $== n -1$

• connections[i].length $== 2$

• $0 \leq a_i, b_i \leq n - 1$

Solution

This algorithm works because representing the network as a graph with directional information allows us to easily identify which roads are misoriented. By performing a DFS from the capital (city $0$), we traverse the entire network exactly once. Every time we encounter a road directed away from city $0$, we know it needs to be reversed. This approach takes advantage of the network’s tree structure to ensure we only count the minimum number of necessary reversals.

Now, let’s look at the solution steps below:

1. Build an adjacency list using a variable graph to store the roads and their directional flags.

   1. For each connection $[a_i, b_i]$ in connections:

      1. Append $(b_i, 1)$ to graph[ai], where the flag$1$ indicates that the road goes from $a_i$ to $b_i$ and might need to be reversed.

      2. Append $(a_i, 0)$ to graph[bi], where the flag $0$ represents the reverse edge, which is correctly oriented for the DFS.

2. Create a set, visited, to track which cities have been processed, preventing repeated visits.

3. Call dfs(0, graph, visited) to start the DFS from the capital (city $0$) and store the result in a variable result.

4. Return result as the final answer is the minimum number of road reorientations needed.

Define the DFS function:

1. Start the DFS from city $0$:

   1. Add the current city to the visited set.

   2. Initializes a variable, reversals, to count the number of road reversals needed for the subtree rooted at that city.

   3. For each neighbor and its associated flag (represented by needReverse) in graph[city]:

      1. If the neighbor hasn’t been visited, add needReverse to result (As needReverse equals $1$ if the road needs reversal).

      2. Recursively call dfs(neighbor, graph, visited) to continue the traversal.

   4. Returns reversals.

Let’s look at the following illustration to get a better understanding of the solution: