#1466

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Reorder Routes to Make All Paths Lead to the City Zero

Reorder Routes to Make All Paths Lead to the City Zero involves reversing the direction of roads in a tree to ensure all cities can reach city 0.

depth first search breadth first search graph

Problem Statement

You are given a network of n cities connected by n - 1 roads. The roads form a tree where each road is directed in one direction, and the roads are represented by an array of pairs. Each pair [ai, bi] represents a road from city ai to city bi. Your goal is to ensure that all cities can reach city 0 by potentially reversing the direction of some roads.

The problem asks you to find the minimum number of roads you must reverse to achieve this. The graph is undirected by nature, but the roads have initial directions, and you need to identify which roads need to be reversed to make every city reachable from city 0.

Examples

Example 1

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

Output: 3

Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2

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

Output: 2

Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 3

Input: n = 3, connections = [[1,0],[2,0]]

Output: 0

Example details omitted.

Constraints

2 <= n <= 5 * 104
connections.length == n - 1
connections[i].length == 2
0 <= ai, bi <= n - 1
ai != bi

Solution Approach

Graph Representation

Represent the cities and roads as a graph using adjacency lists. Since the graph is a tree, it has a root at city 0. Each road is directed, but we treat it as undirected when traversing with DFS. We reverse edges as needed based on traversal direction.

Depth-First Search (DFS)

Use DFS to explore the graph starting from city 0. For each road, if the traversal encounters a directed road pointing away from the current city, reverse that road to ensure connectivity. Keep track of the reversed roads to minimize the number of changes.

Optimization

The problem constraints allow for an O(n) solution. By using DFS, we can traverse all cities and check the direction of each road in linear time. The space complexity remains O(n) due to the adjacency list and recursive calls during DFS.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) due to the need to traverse each city and road exactly once. The space complexity is O(n) as well, required for storing the graph structure and recursion stack in DFS.

What Interviewers Usually Probe

Check for efficient DFS implementation and graph traversal logic.
Look for correct handling of edge reversal during traversal.
Evaluate the candidate's understanding of graph traversal patterns, especially DFS on tree structures.

Common Pitfalls or Variants

Common pitfalls

Treating the graph as directed instead of undirected during traversal.
Incorrectly reversing edges or failing to track reversed roads.
Forgetting to account for the minimum number of reversals needed.

Follow-up variants

What if the graph was a directed acyclic graph (DAG) instead of a tree?
How would the problem change if there were multiple potential sources instead of just city 0?
Consider adding additional constraints like road weight or city types. How would this affect your approach?

FAQ

How do I approach the Reorder Routes to Make All Paths Lead to the City Zero problem?

Start by treating the graph as undirected, then use DFS to explore from city 0. Reverse edges when encountering roads pointing away from city 0.

What is the optimal time complexity for this problem?

The optimal time complexity is O(n), where n is the number of cities. This can be achieved using DFS traversal.

How does DFS help in solving this problem?

DFS helps explore all cities and roads, ensuring we can reverse the necessary roads to make all cities accessible from city 0.

Why is this problem classified under Graph Traversal and DFS?

This problem requires traversing a graph (tree structure) and reversing edges based on direction, which is a classic DFS traversal task.

What is the space complexity of this solution?

The space complexity is O(n), which is needed for storing the adjacency list and the recursion stack during DFS.

terminal

Solution

Solution 1: DFS

The route map given in the problem has $n$ nodes and $n-1$ edges. If we ignore the direction of the edges, then these $n$ nodes form a tree. The problem requires us to change the direction of some edges so that each node can reach node $0$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        def dfs(a: int, fa: int) -> int:
            return sum(c + dfs(b, a) for b, c in g[a] if b != fa)

        g = [[] for _ in range(n)]
        for a, b in connections:
            g[a].append((b, 1))
            g[b].append((a, 0))
        return dfs(0, -1)

Solution 2: BFS

We can use the Breadth-First Search (BFS) method, starting from node $0$, to search all other nodes. During the process, if we encounter an edge that requires a change of direction, we increment the count of direction changes.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        def dfs(a: int, fa: int) -> int:
            return sum(c + dfs(b, a) for b, c in g[a] if b != fa)

        g = [[] for _ in range(n)]
        for a, b in connections:
            g[a].append((b, 1))
            g[b].append((a, 0))
        return dfs(0, -1)

Continue Practicing

#1462 course schedule iv #1377 frog position after t seconds #1361 validate binary tree nodes