How do you solve Minimum Number of Edge Reversals to Reach City Zero?

Build an undirected adjacency list for traversal and a set of directed edges representing original directions. Perform DFS from node 0, marking visited nodes. For each neighbor, if the edge is directed from current node to neighbor, increment reversal count. Recursively accumulate reversals from all reachable nodes. Return the total count as the minimum number of edges to reverse.

Minimum Number of Edge Reversals to Reach City Zero

Q: What is the time complexity of Minimum Number of Edge Reversals to Reach City Zero?

O(n). Each node and edge is visited exactly once during DFS traversal. Building the graph and set of edges also takes O(n). Thus, total time complexity is linear in the number of nodes.

Q: What pattern does Minimum Number of Edge Reversals to Reach City Zero use?

The Pattern: DFS (Graph Traversal with Edge Direction Tracking) The Heuristic: When needing to count or modify edge directions to achieve a global connectivity property, transform the graph into an undirected form for traversal while tracking original edge directions separately to identify necessary changes during DFS.

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 road from city a to city b, return the minimum number of edges that must be reversed so that there is a path from every city to 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

Take n = 6 and connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]. First, we separate traversal from direction: - We build an undirected adjacency list so that starting from city 0, DFS can reach every city, regardless of how roads are currently oriented. - In parallel, we store every original directed road (a, b) in a set roads so we can later check, in O(1), whether a given move follows the original direction. For this example: roads = {(0,1), (1,3), (2,3), (4,0), (4,5)} Now we run DFS from city 0 with visited = {0}. 1) From city 0, the undirected neighbors are 1 and 4. - Suppose DFS goes to 1 first. - We are moving along edge (0, 1). Since (0,1) is in roads, this road currently points away from city 0. - To allow city 1 (and everything beyond it) to reach 0, this edge must be reversed, so we count 1 reversal. 2) At city 1, the neighbors are 0 and 3. - 0 is already visited, so we move to 3. - We follow edge (1, 3). Because (1,3) is in roads, it also points away from 0. - That means we must reverse this edge as well, so our total becomes 2. 3) At city 3, the neighbors are 1 and 2. - 1 is already visited, so we move to 2. - We follow edge (3, 2). The original roads set contains (2,3), not (3,2), so (3,2) is not in roads. - This means, in the original graph, the edge was oriented from 2 to 3, which is actually toward the path back to 0. We do not need to reverse this one, so the count stays at 2. 4) After finishing the subtree from city 1, DFS backtracks to city 0 and then explores the other neighbor, city 4. - We move along edge (0, 4). The original roads set contains (4,0) instead of (0,4), so (0,4) is not in roads. - That means this road already points toward 0 in the original graph, so no reversal is needed here. 5) From city 4, the unvisited neighbor is 5. - We follow edge (4, 5). Since (4,5) is in roads, this road points away from 0. - We must reverse it so that city 5 can eventually reach city 0, bringing our total to 3 reversals. By the time DFS finishes, every city has been visited once, and we have counted exactly the roads that pointed "the wrong way" relative to city 0. The final answer for this example is 3, which is the minimum number of edges to reverse so that all cities can reach city 0.

Approach

Straightforward Solution

A brute-force idea is to ignore the tree structure and repeatedly re-check reachability. For example, you might start a traversal from every city to see if it can reach city 0, doing O(n) work for each of the n cities. This leads to roughly O(n^2) behavior and wastes work by re-walking the same subtrees over and over.

Core Observation

The problem reduces to ensuring all nodes can reach node 0 by reversing edges that point away from 0. Representing the graph as undirected allows traversal of all nodes, while a separate set tracks original edge directions to identify which edges need reversal.

Path to Optimal

Preview

The key insight is to treat the graph as undirected for traversal, but keep track of original edge directions. Starting DFS from node 0, whenever an edge leads from the current node to a neighbor in the original direction, it must be reversed to allow travel back to 0…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an undirected adjacency list for traversal and a set of directed edges representing original directions. Perform DFS from node 0, marking visited nodes…

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 exactly once during DFS traversal. Building the graph and set of edges also takes O(n). Thus, total time complexity is linear in the number of nodes.

Space

O(n)

The adjacency list and set of edges each store O(n) elements. The recursion stack in DFS can go up to O(n) in the worst case. This auxiliary space is necessary to represent the graph and track visited nodes.

Pattern Spotlight

DFS (Graph Traversal with Edge Direction Tracking)

When needing to count or modify edge directions to achieve a global connectivity property, transform the graph into an undirected form for traversal while tracking original edge directions separately to identify necessary changes during DFS.

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

Construct 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 build an undirected adjacency list for traversal and a set to record original directed edges for reversal checks.

Key Insight

Transforming the directed graph into an undirected one allows DFS to reach all nodes regardless of edge direction. The set of original edges preserves direction information, enabling the algorithm to detect which edges need reversal during traversal. This separation of concerns simplifies traversal logic and reversal counting.

Interview Quick-Check

Core Logic

Building an undirected graph ensures full connectivity traversal, while the set of directed edges tracks which edges originally point away from node 0.

Common Pitfalls & Bugs

Forgetting to add edges in both directions to the adjacency list would prevent traversal to some nodes.

State & Boundaries

The set stores tuples (x, y) representing edges directed from x to y, enabling O(1) checks during DFS.

Perform DFS Traversal to Count Required Edge Reversals

To recursively explore all nodes from city 0, counting edges that must be reversed to enable travel back to city 0.

Initialize Visited Set and Return Final Reversal Count

To start DFS from city 0 with the visited set initialized and return the total number of edge reversals required.

2 more steps 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 current node to neighbor is in the original directed edges set.

This check identifies edges directed away from node 0 that must be reversed to enable 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 and infinite recursion, ensuring each node is processed once.

Line 16 Critical

seen.add(neighbor)

Mark the neighbor as visited before recursive DFS call.

Adding the neighbor to the visited set before recursion prevents cycles and repeated processing.

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

Test Your Understanding

Why does representing the graph as undirected and tracking original edge directions separately enable counting the minimum reversals in a single DFS?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Number of Edge Reversals to Reach City Zero from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Number of Edge Reversals to Reach 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))`