Reorder Routes using Python

Reorder routes to make all paths lead to the city zero is a popular question in coding interviews. In this problem, you need to reorder the connections between the cities so that all paths lead to the city labelled as zero. So, if you want to learn how to reorder routes using Python, this article is for you. In this article, I will take you through how to reorder routes to make all paths lead to the city zero using Python.

Reorder Routes to Make All Paths Lead to the City Zero

In the problem of reordering routes to make all paths lead to city zero, you will be given an array of connections between cities in pairs of integers. Each connection will show a one-way route from one city to another. For example, [1, 0] means that there is a one-way road from city 1 to city 0. Your task is to reorder the connections such that each city can be reached from city 0, directly or indirectly. The output value should return the minimum number of edges changed.

Here’s an example of the input and output values of this problem:

• Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] | Output = 2

In the above example, the output is 2 because we need to reverse two connections to make all paths lead to city zero.

Reorder Routes using Python

I hope you have understood what the problem of reordering routes to make all paths lead to the city zero means. Now here’s how to reorder routes using Python:

from collections import defaultdict
def minReorder(n, connections):
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append((v, 1))
        graph[v].append((u, 0))
            
    def dfs(node):
        nonlocal total
        visited.add(node)
            
        for neighbor, cost in graph[node]:
            if neighbor not in visited:
                total += cost
                dfs(neighbor)
    total = 0
    visited = set()
    dfs(0)
    return total

n = 6
connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
print(minReorder(n, connections))

Output: 3

Below is how the above code works:

1. We started by creating a graph showing all the connected routes. It then walks through each route and checks whether it is one-way or not.
2. If a route is one-way, we’ve added “cost” to that route to indicate that it needs to be changed. This “cost” tracks how many paths need to be changed.
3. Finally, we used a depth-first search algorithm to go through all the routes and find how many need to be reordered.
4. Then, it returns the total number of reordered routes.

So this is how you can reorder routes using Python. You can find many more practice questions for coding interviews solved and explained using Python here.

Summary

Reorder routes to make all paths lead to the city zero is a popular question in coding interviews. In this problem, you need to reorder the connections between the cities so that all paths lead to the city labelled as zero. I hope you liked this article on how to reorder routes using Python. Feel free to ask valuable questions in the comments section below.