Reorder Routes to Make All Paths Lead to the City Zero – LeetCode75 Python Solution Explained

The Reorder Routes to Make All Paths Lead to the City Zero problem (LeetCode75) is a graph problem that tests your understanding of DFS traversal, graph representation and edge direction handling. It is commonly asked in technical interviews to assess your problem-solving skills with directed graphs and connectivity analysis.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You are given n cities numbered from 0 to n-1 and a list of connections representing directed roads between cities. Each connection [a, b] means there is a road from city a to city b.

Your task is to reorder the minimum number of roads so that every city can reach city 0. Return the minimum number of edges that need to be reversed.

Example 1

Input:

n = 6
connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]

Output:

3

Explanation:

Reversing roads [1,3], [2,3], [4,5] ensures every city can reach city 0.

Example 2

Input:

n = 5
connections = [[1,0],[1,2],[3,2],[3,4]]

Output:

2

Complete Python Solution

from typing import List

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        
        # Build the graph with direction info
        for u, v in connections:
            graph[u].append((v,1))  # original direction
            graph[v].append((u,0))  # reverse direction
        
        def dfs(node, parent):
            nonlocal count
            for neighbor, direction in graph[node]:
                if neighbor != parent:
                    count += direction
                    dfs(neighbor, node)
        
        count = 0
        dfs(0, -1)
        return count

Step-by-Step Explanation

Step 1: Build the Graph

Represent the graph as an adjacency list with direction flags:

• 1 → edge points away from the city (needs to be reversed if traversed).
• 0 → edge points toward the city (already correct).

graph = [[] for _ in range(n)]
for u, v in connections:
    graph[u].append((v,1))
    graph[v].append((u,0))

Step 2: Define DFS Function

Perform DFS traversal starting from city 0.

• Track parent to avoid revisiting the previous city.
• Increment count if an edge points away from city 0 (needs reversal).

def dfs(node, parent):
    nonlocal count
    for neighbor, direction in graph[node]:
        if neighbor != parent:
            count += direction
            dfs(neighbor, node)

Step 3: Initialize Counter and Start DFS

count = 0
dfs(0, -1)

• Start DFS from city 0 with parent -1 (no parent).
• count will track the number of edges to reverse.

Step 4: Return the Result

return count

• After DFS, count contains the minimum edges to reorder.

Time and Space Complexity

• Time Complexity:O(n)
  • Each node and edge is visited once.
• Space Complexity:O(n)
  • Adjacency list storage and recursion stack for DFS.

Edge Cases

1. All cities already lead to 0: count = 0
2. Single city: n = 1 → count = 0
3. Linear chain away from city 0: Needs all edges reversed

Real-World Applications

• Road Network Optimization: Ensure connectivity to a central hub.
• Packet Routing in Networks: Reverse or update routes to ensure all nodes can reach the main server.
• Logistics and Supply Chain: Adjust routes so that all branches can send goods to a central warehouse.
• Urban Planning: Determine minimum changes needed to make all roads accessible to the main city.

Conclusion

The Reorder Routes to Make All Paths Lead to the City Zero problem is a great exercise in DFS traversal, directed graphs and edge orientation handling. By analyzing the graph with direction flags and recursively visiting all cities, we can efficiently compute the minimum number of road reversals required.

This problem enhances your understanding of:

• Recursive DFS traversal
• Graph representation with edge directions
• Connectivity in directed graphs

It is highly valuable for technical interviews and practical applications in networks, logistics and urban planning.

Related Reads

• Evaluate Division – LeetCode75 Python Solution Explained
• Nearest Exit from Entrance in Maze – LeetCode75 Python Solution Explained
• Keys and Rooms – LeetCode75 Python Solution Explained
• Smallest Number in Infinite Set – LeetCode75 Python Solution Explained
• Maximum Subsequence Score – LeetCode75 Python Solution Explained

References

1. LeetCode – Reorder Routes to Make All Paths Lead to the City Zero
2. GeeksforGeeks – Graph DFS Tutorial
3. Graph Theory Applications