Reorder Routes To Make All Paths Lead To The City Zero - Leetcode Solution

Problem Statement:

You are given a list of routes, where routes[i] = [start_i, end_i] represents a direct route between two cities. Each city is labeled with a different integer from 0 to n - 1.

You want to make all the cities connected to the city zero. So, you begin with the city zero and can visit any city by traveling through the direct routes.

Return the minimum number of edges to travel to connect all the cities.

Example 1: Input: n = 6, connections = [[0,1],[0,2],[3,4],[2,3],[1,2]] Output: 3 Explanation: The optimal strategy is as follows:

• Connect cities 0 and 1 together
• Connect cities 0 and 2 together
• Connect cities 2 and 3 together Minimum number of edges to connect all cities is 3, which is the path of 0 -> 1 -> 2 -> 3.

Solution:

To solve this problem, we can use the Breadth First Search (BFS) algorithm. We can start the search from the source node, which is 0 in this problem, and traverse all the connected nodes. During the traversal, we can keep track of the visited nodes and add the unvisited nodes to a queue. We can continue this process until we have traversed all the connected nodes.

Now, we need to reorder the paths such that they all lead to city zero. To do this, we can create a tree with the source node at the root and all the connected nodes as its children. We can then traverse the tree in post-order and keep track of the number of edges for each node. The number of edges for a node is the number of edges required to reach it from its children. We can then add this number to the total number of edges required to reach the parent node. We can continue this process until we have computed the number of edges for all the nodes.

At each node, we can check if the number of edges required to reach the parent node is less than or greater than the number of edges required to reach the node from its parent. If it is less than the number of edges required to reach the node from its parent, we need to reorder the paths.

To reorder the paths, we can swap the start and end nodes of the path. We can then add the path to a list of reordered paths. We can continue this process until we have reordered all the paths.

Finally, we can return the number of reordered paths as the minimum number of edges required to connect all the cities.

Code:

The code for the above solution is as follows:

from collections import defaultdict, deque

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in connections:
            graph[u].append((v, 1))
            graph[v].append((u, 0))

        visited = [False] * n
        visited[0] = True

        queue = deque([0])
        while queue:
            node = queue.popleft()
            for neighbor, direct in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)
                    graph[node].remove((neighbor, direct))
                    graph[neighbor].append((node, direct))

        reorder_count = 0
        visited = [False] * n
        visited[0] = True

        def dfs(node):
            nonlocal reorder_count
            for neighbor, direct in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    dfs(neighbor)
                    if direct == 1:
                        reorder_count += 1
                else:
                    if direct == 0:
                        reorder_count += 1

        dfs(0)
        return reorder_count

Explanation:

The above code first creates an adjacency list to represent the graph. For each edge (u, v), we add v to the adjacency list of u with a weight of 1, and we add u to the adjacency list of v with a weight of 0. The weight of an edge represents whether we need to reorder the path or not.

We then use BFS to traverse all the connected nodes from the source node 0. During the traversal, we update the adjacency list of each node by removing the incoming edge and adding a new outgoing edge with the same weight.

We then use DFS to traverse the tree in post-order and compute the number of edges required to reach each node. We also keep track of the number of reordered paths.

At each node, we check whether the number of edges required to reach the parent node is less than or greater than the number of edges required to reach the node from its parent. If it is less, we increment the number of reordered paths and swap the start and end nodes of the path.

Finally, we return the number of reordered paths as the minimum number of edges required to connect all the cities.

1