Minimum Number of Edge Reversals to Reach City Zero
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
n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]3Take 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
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. This approach counts reversals during a single DFS traversal, ensuring O(n) time complexity.
Optimal Approach
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.
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
| 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) |
Step-by-Step Solution
Construct Undirected Graph and Track Original Directed Edges
| 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))
|
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
| 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)
|
| 19 | return ans
|
Objective
To recursively explore all nodes from city 0, counting edges that must be reversed to enable travel back to city 0.
Key Insight
DFS explores neighbors of the current node. If the edge from current node to neighbor exists in the original directed edges set, it means the edge points away from city 0 and must be reversed. By accumulating these counts recursively, the algorithm efficiently computes the minimum reversals needed for full connectivity to city 0.
Interview Quick-Check
Core Logic
DFS visits each neighbor not yet seen, increments reversal count if the edge is directed away from the traversal source, and accumulates counts from recursive calls.
State & Boundaries
The visited set prevents revisiting nodes and infinite recursion.
Common Pitfalls & Bugs
Failing to add neighbors to the visited set before recursive calls can cause infinite loops.
Initialize Visited Set and Return Final Reversal Count
| 21 | seen = {0}
|
| 22 | return dfs(0) |
Objective
To start DFS from city 0 with the visited set initialized and return the total number of edge reversals required.
Key Insight
Initializing the visited set with city 0 ensures the traversal starts correctly and prevents revisiting the start node. Returning the DFS result directly provides the minimum number of reversals needed for all cities to reach city 0.
Interview Quick-Check
Core Logic
Starting DFS from node 0 with visited set initialized ensures correct traversal and accurate reversal counting.
State & Boundaries
The visited set tracks all nodes already explored to avoid cycles.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
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.
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.
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.
ans += dfs(neighbor)Recursively call DFS on the neighbor and add its reversal count.
This recursive accumulation ensures the total reversal count includes all edges in the subtree rooted at the neighbor.
roads = set()Initialize a set to store original directed edges.
This set enables O(1) checks to determine if an edge is directed from a node to its neighbor, which is critical for counting reversals during DFS.
roads.add((x, y))Add the original directed edge (x, y) to the roads set.
Storing the original edge direction is essential to identify which edges need reversal during DFS traversal.
ans += 1Increment reversal count if the edge must be reversed.
Counting this edge here accumulates the total number of reversals needed for connectivity to node 0.
return ansReturn the total reversal count for the current node's subtree.
Returning this value allows parent calls to aggregate reversal counts correctly, enabling a full count from the root.
return dfs(0)Return the total number of edge reversals needed by invoking DFS from city 0.
This final return provides the minimum number of edges to reverse so all cities can reach city 0.
graph = defaultdict(list)Create a default dictionary to represent the undirected graph adjacency list.
Using a defaultdict of lists simplifies graph construction and allows efficient neighbor lookups during traversal.
graph[x].append(y)Add neighbor y to adjacency list of x.
Adding this edge allows traversal from x to y in the undirected graph representation.
graph[y].append(x)Add neighbor x to adjacency list of y.
Adding this edge allows traversal from y to x, ensuring the graph is undirected for full connectivity.
for neighbor in graph[node]:Iterate over all neighbors of the current node.
Exploring all neighbors is necessary to traverse the entire graph and count reversals for all edges.
seen = {0}Initialize the visited set with city 0 as starting point.
Starting with city 0 visited ensures DFS begins correctly and prevents revisiting the root node.
def dfs(node):Define the DFS function to explore nodes and count reversals.
Encapsulating traversal and reversal counting in a recursive function enables clean, modular exploration of the graph.
ans = 0Initialize the reversal count accumulator for the current node.
This variable tracks the number of edges needing reversal in the subtree rooted at the current node.
for x, y in connections:Iterate over each directed edge in connections.
Processing each edge is necessary to build the undirected graph and record original directions.
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?
Because the undirected graph ensures all nodes are reachable during traversal, while the separate set of original directed edges allows identifying which edges point away from the traversal source (node 0). Counting edges directed from current node to neighbor during DFS directly corresponds to edges that must be reversed to enable travel back to node 0.
Related Problems
DFS pattern
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