Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Reorder Routes to Make All Paths Lead to the City Zero
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given n cities labeled from 0 to n-1 and n-1 roads, which form a tree structure. Each road is directed, meaning it has a specific direction. These roads are represented by the array connections, where connections[i] = [a, b] indicates a road from city a to city b.

Change the direction of some roads so that every city can reach city 0.

Return the minimum number of edges that need to be reversed.

Examples

Example 1

  • Input: n = 5, connections = [[0, 1], [1, 2], [2, 3], [4, 3]]
Image
  • Expected Output: 3
  • Justification: To make all cities lead to city 0, reverse the roads [0, 1], [1, 2] and [2, 3]. This will make the paths 0 <- 1 <- 2 <- 3 <- 4.

Example 2

  • Input: n = 6, connections = [[0, 1], [2, 0], [3, 2], [4, 3], [5, 3]]
Image
  • 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<sub>i</sub>, b<sub>i</sub> <= n - 1
  • a<sub>i</sub> != b<sub>i</sub>

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

Python3
Python3

. . . .

Complexity Analysis

Time Complexity

The time complexity of the algorithm is O(n), where (n) is the number of cities (nodes) in the graph. This is because we are visiting each node exactly once and processing each edge (road) exactly twice (once for each direction).

Space Complexity

The space complexity of the algorithm is also O(n). This is due to the space required for:

  • The adjacency list representation of the graph.
  • The boolean array used to keep track of visited nodes.
  • The call stack for the depth-first search (DFS) recursion, which, in the worst case, can go up to O(n) levels deep.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible