How do you solve Reorder Routes to Make All Paths Lead to the City Zero?

Build an undirected graph from the connections to allow traversal in both directions. Store the original directed edges in a set for quick lookup. Perform DFS starting from node 0, marking visited nodes. For each neighbor, if the edge from the current node to the neighbor exists in the original direction set, increment the reversal count. Recursively accumulate the count from all reachable nodes. Return the total count after DFS completes.

Reorder Routes to Make All Paths Lead to the City Zero

Q: What is the time complexity of Reorder Routes to Make All Paths Lead to the City Zero?

O(n). Each node and edge is visited once during DFS. Building the graph and the set of edges also takes O(n) time.

Q: What pattern does Reorder Routes to Make All Paths Lead to the City Zero use?

The Pattern: DFS (Graph Traversal with Edge Direction Tracking) The Heuristic: When needing to reorient edges to ensure reachability to a root node, convert the graph to undirected for traversal while tracking original edge directions; count reversals when traversing edges that point away from the root.

Medium DFS

Problem

Given n cities numbered from 0 to n-1 and a list of directed connections where connections[i] = [a, b] represents a directed edge from city a to city b, return the minimum number of edges that must be reversed so that every city can reach city 0.

2 ≤ n ≤ 5 * 10⁴
connections.length == n - 1
connections[i].length == 2
0 ≤ connections[i][0], connections[i][1] ≤ n - 1
All cities are connected

Example

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

Output: 3

Starting from city 0, the algorithm builds an undirected graph to explore all cities. It tracks the original direction of edges in a set. When traversing from city 0, it visits neighbors. If the edge from the current city to the neighbor exists in the original direction set, it means this edge must be reversed to allow travel back to city 0, so the count increments. For example, edge (0,1) is directed away from city 0 and must be reversed. Similarly, edges (1,3) and (4,5) must be reversed. The total count is 3.

Approach

Straightforward Solution

A brute-force approach might try all permutations of edge reversals, which is computationally infeasible due to exponential complexity.

Core Observation

The problem reduces to ensuring all nodes can reach node 0 by reversing the minimum number of edges. The key insight is that the original directed edges that point away from node 0 must be reversed, while edges that already point towards node 0 do not need changes.

Path to Optimal

Preview

By treating the graph as undirected for traversal and keeping track of original edge directions, the problem becomes a DFS traversal starting from node 0…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an undirected graph from the connections to allow traversal in both directions. Store the original directed edges in a set for quick lookup…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node and edge is visited once during DFS. Building the graph and the set of edges also takes O(n) time.

Space

O(n)

The adjacency list and the set of edges each store O(n) elements. The recursion stack in DFS can go up to O(n) in the worst case.

Pattern Spotlight

DFS (Graph Traversal with Edge Direction Tracking)

When needing to reorient edges to ensure reachability to a root node, convert the graph to undirected for traversal while tracking original edge directions; count reversals when traversing edges that point away from the root.

Solution

Python

1class Solution:
  def minReorder(self, n: int, connections: List[List[int]]) -> int:
      roads = set()
      graph = defaultdict(list)
      for x, y in connections:
          graph[x].append(y)
          graph[y].append(x)
          roads.add((x, y))
9
      def dfs(node):
          ans = 0
          for neighbor in graph[node]:
              if neighbor not in seen:
                  if (node, neighbor) in roads:
                      ans += 1
                  seen.add(neighbor)
                  ans += dfs(neighbor)
          
          return ans
20
      seen = {0}
      return dfs(0)

Step-by-Step Solution

Build Undirected Graph and Track Original Directed Edges

3roads = set()
4graph = defaultdict(list)
5for x, y in connections:
6    graph[x].append(y)
7    graph[y].append(x)
8    roads.add((x, y))

Objective

To construct a data structure that supports traversal in both directions while remembering the original edge directions.

Key Insight

By creating an undirected graph, the algorithm can explore all nodes from the root without missing any due to direction constraints. Storing the original directed edges in a set allows quick determination of whether an edge needs reversal during traversal.

Interview Quick-Check

Core Logic

The undirected graph enables full traversal, while the set of original edges identifies which edges are directed away from the current node and thus require reversal.

Common Pitfalls & Bugs

Forgetting to add edges in both directions to the graph or failing to track original edge directions leads to incorrect reversal counts.

Perform DFS Traversal to Count Required Edge Reversals

To recursively explore all reachable nodes from city 0, counting edges that must be reversed to ensure all paths lead to city 0.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 14 Critical

if (node, neighbor) in roads:

Check if the edge from the current node to the neighbor exists in the original directed edges set.

If this edge exists, it means the edge is directed away from the current node and must be reversed to allow travel back to node 0.

Line 13 Critical

if neighbor not in seen:

Check if the neighbor has not been visited yet.

This condition prevents revisiting nodes, avoiding infinite recursion and double counting.

Line 15 Critical

ans += 1

Increment the reversal count because this edge must be reversed.

Counting this edge here ensures the final answer reflects the minimal number of reversals needed to make all paths lead to node 0.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why does traversing the graph as undirected and checking the original edge direction allow counting the minimum number of reversals?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Reorder Routes to Make All Paths Lead to the City Zero from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Reorder Routes to Make All Paths Lead to the City Zero drill

or drill a free problem

1	`class Solution:`
2	`def minReorder(self, n: int, connections: List[List[int]]) -> int:`
3	`roads = set()`
4	`graph = defaultdict(list)`
5	`for x, y in connections:`
6	`graph[x].append(y)`
7	`graph[y].append(x)`
8	`roads.add((x, y))`
9
10	`def dfs(node):`
11	`ans = 0`
12	`for neighbor in graph[node]:`
13	`if neighbor not in seen:`
14	`if (node, neighbor) in roads:`
15	`ans += 1`
16	`seen.add(neighbor)`
17	`ans += dfs(neighbor)`
18
19	`return ans`
20
21	`seen = {0}`
22	`return dfs(0)`

3	`roads = set()`
4	`graph = defaultdict(list)`
5	`for x, y in connections:`
6	`graph[x].append(y)`
7	`graph[y].append(x)`
8	`roads.add((x, y))`