We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reorder Routes to Make All Paths Lead to the City Zero

Number: 1576

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, TikTok, Bloomberg, Docusign

Problem Description

Given n cities (numbered from 0 to n - 1) connected by n - 1 directed roads forming a tree, we need to reorient the minimum number of roads so that every city can reach the capital, city 0.

Key Insights

  • The underlying graph forms a tree, so there is exactly one unique path between any pair of cities.
  • By converting the problem to an undirected graph while keeping track of the original directed edges, we can traverse the tree starting from city 0.
  • During traversal, if an edge is oriented away from the current node (i.e. in the original direction), it must be reversed in order for the path to lead to city 0.
  • A DFS or BFS can be used to count the minimum number of edge reversals needed.

Space and Time Complexity

Time Complexity: O(n), where n is the number of cities, since we traverse each edge exactly once. Space Complexity: O(n), for storing the graph and the recursion/queue for traversal.

Solution

The approach is to convert the directed tree into an undirected graph while tagging each edge with a flag indicating its original orientation. For each directed edge from a to b:

  • Add an edge (b, 1) to a’s list, indicating that if we travel from a to b, the edge is in the original forward direction and will require a reversal.
  • Also add an edge (a, 0) to b’s list, which represents the reversed edge that does not require changing if we go from b to a. Starting the traversal from city 0 ensures that every visited edge leading out from 0 must be reversed. We then perform a DFS (or BFS) to visit all the cities while tracking and counting the edges that require reorientation. This method guarantees that all nodes will eventually reach city 0 with a minimal number of changes.

Code Solutions

# Python solution for the problem

def minReorder(n, connections):
    # Build the graph as a dictionary where each key is a city and each value is a list of tuples (neighbor, cost)
    graph = {i: [] for i in range(n)}
    for a, b in connections:
        # Edge from a to b requires reversal if from a to b (cost = 1)
        graph[a].append((b, 1))
        # From b to a, the edge is in the reverse direction so no change is needed (cost = 0)
        graph[b].append((a, 0))
    
    # Use DFS to traverse from city 0 and count the required reorders
    visited = set()
    
    def dfs(city):
        visited.add(city)
        changes = 0
        # Traverse all neighbors of the current city
        for neighbor, cost in graph[city]:
            if neighbor not in visited:
                # Add the current cost if the edge is in the original direction (cost 1 means reversal needed)
                changes += cost + dfs(neighbor)
        return changes
        
    return dfs(0)

# Example usage:
n = 6
connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
print(minReorder(n, connections))  # Output should be 3
← Back to All Questions