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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reorder Routes to Make All Paths Lead to the City Zero

Difficulty: Medium

Problem Description

Given n cities numbered from 0 to n - 1 and n - 1 roads represented by connections where connections[i] = [a_i, b_i] indicates a one-way road from city a_i to city b_i, the task is to reorient some roads such that every city can reach city 0. The goal is to return the minimum number of edges that need to be changed.

Key Insights

  • The cities and roads form a tree structure since there are n nodes (cities) and n - 1 edges (roads).
  • Each city must eventually reach city 0, which is the root of the tree.
  • Reorienting a road from b to a is necessary if the current road goes from a to b and city b is not directly leading to city 0.
  • A depth-first search (DFS) or breadth-first search (BFS) can be used to traverse the tree and count the required reorientations.

Space and Time Complexity

Time Complexity: O(n) - We visit each edge once during the traversal. Space Complexity: O(n) - For storing the graph representation and recursion stack (in the case of DFS).

Solution

To solve the problem, we represent the cities and roads as a directed graph using an adjacency list. We then perform a DFS traversal starting from city 0, counting how many edges need to be reversed to ensure all cities can reach city 0. During the traversal, we check the direction of each edge and increment our count whenever we encounter an edge that does not point towards city 0.

Code Solutions

def minReorder(n, connections):
    from collections import defaultdict

    # Create a graph with edges in both directions
    graph = defaultdict(list)
    for a, b in connections:
        graph[a].append((b, 1))  # 1 indicates original direction
        graph[b].append((a, 0))  # 0 indicates reversed direction

    def dfs(city, parent):
        changes = 0
        for neighbor, direction in graph[city]:
            if neighbor != parent:  # Avoid going back to the parent node
                changes += direction  # Count if the road is in original direction
                changes += dfs(neighbor, city)  # Recur for the neighbor
        return changes

    return dfs(0, -1)  # Start DFS from city 0
← Back to All Questions