• Expected Output: 1
• Justification: To make all cities lead to city 0, reverse the road [0, 1].

Example 3

• Input: n = 4, connections = [[1, 0], [2, 1], [3, 2]]
• Expected Output: 0
• Justification: All cities have path from itself to 0. So, we don't need to reverse any edge.

Constraints:

• 2 <= n <= 5 * 10<sup>4<sup>
• connections.length == n - 1
• connections[i].length == 2
• 0 <= a_i, b_i <= n - 1
• a_i != b_i

Solution

To solve this problem, we can use Depth-First Search (DFS). The key idea is to count the roads that need to be reversed to ensure all cities can reach city 0. We will traverse the graph using DFS, starting from city 0. During the traversal, if a road leads away from city 0, it means we need to reverse it. We will keep a count of such roads and continue the DFS traversal to cover all cities.

This approach is effective because it leverages the properties of a tree structure (connected and acyclic) and the given constraints (every city can reach city 0 after reordering). DFS allows us to explore all possible paths efficiently, ensuring we count the minimum number of reversals needed.

Step-by-Step Algorithm

1. Create a graph representation:

   • Use an adjacency list to represent the graph.
   • Add both directions of each road to the adjacency list to handle undirected traversal.
   • If a road is from a to b, store it as (b, 1) in a's list and (a, 0) in b's list. Here, 1 means the original direction needs to be reversed, and 0 means no reversal is needed.

2. Initialize a set to track visited cities:

   • Use a HashSet to keep track of visited nodes to avoid cycles.

3. Perform DFS traversal:

   • Start the DFS from city 0.
   • For each neighboring city, check if it is already visited.
   • If not visited, check if the road direction needs to be reversed.
   • Increment the change counter if a reversal is needed.
   • Recur for the neighboring cities.

4. Count the number of road reversals needed:

   • Sum the number of reversals needed as you traverse each city.

Algorithm Walkthrough

Using the input: n = 5, connections = [[0, 1], [1, 2], [2, 3], [4, 3]]

1. Graph Construction:

   • Initialize the graph as an adjacency list.
   • Add both directions for each road:

     graph[0] = [(1, 1)]
     graph[1] = [(0, 0), (2, 1)]
     graph[2] = [(1, 0), (3, 1)]
     graph[3] = [(2, 0), (4, 0)]
     graph[4] = [(3, 1)]
     

2. Initialize visited set:

   • Initialize an empty set visited.

3. DFS Traversal:

   • Start DFS from node 0.
     • Mark 0 as visited.
     • Traverse neighbors of 0: (1, 1)
       • 1 is not visited.
       • Road (0, 1) needs to be reversed. Increment change counter by 1.
       • Recur DFS from node 1.
         • Mark 1 as visited.
         • Traverse neighbors of 1: (0, 0), (2, 1)
           • 0 is already visited.
           • 2 is not visited.
           • Road (1, 2) needs to be reversed. Increment change counter by 1.
           • Recur DFS from node 2.
             • Mark 2 as visited.
             • Traverse neighbors of 2: (1, 0), (3, 1)
               • 1 is already visited.
               • 3 is not visited.
               • Road (2, 3) needs to be reversed. Increment change counter by 1.
               • Recur DFS from node 3.
                 • Mark 3 as visited.
                 • Traverse neighbors of 3: (2, 0), (4, 0)
                   • 2 is already visited.
                   • 4 is not visited.
                   • Road (4, 3) is in the correct direction. No change needed.
                   • Recur DFS from node 4.
                     • Mark 4 as visited.
                     • Traverse neighbors of 4: (3, 1)
                       • 3 is already visited.
                     • DFS from node 4 completes. Returns 0.
                 • DFS from node 3 completes. Returns 0.
             • DFS from node 2 completes. Returns 1.
         • DFS from node 1 completes. Returns 2.
     • DFS from node 0 completes. Returns 3.

4. Count the number of road reversals needed:

   • Total number of reversals: 3.

Code