NeetCode #571LC-1466MediumGraphs
← Back to All Problems#571 · #1466 · Reorder Routes to Make All Paths Lead to the City Zero(重新规划路线)
📌 Problem Statement & Constraints
There are
n cities numbered 0..n-1 and n - 1 directed roads forming a tree. connections[i] = [a, b] means the road goes from a to b. Reorient some roads so that every city can reach city 0. Return the minimum number of roads to reorient. Constraints: 2 <= n <= 5 * 10^4, connections.length == n - 1.💡 Core Algorithmic Approaches
- Root the tree at city 0 and traverse it.
- For each edge traversed from a parent to a child: if the original direction is parent → child, it points away from 0 and must be reversed; if it is child → parent, it already points toward 0.
- So store, for each undirected edge, the cost of traversing it in each direction (0 or 1).
- Sum the costs along a DFS/BFS from 0 -- each edge is counted exactly once.
💻 Benchmark Python3 Implementation
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
from collections import defaultdict
g = defaultdict(list)
for a, b in connections: # the road currently goes a -> b
g[a].append((b, 1)) # going a -> b means it points away from 0
g[b].append((a, 0)) # going b -> a is already the right way
seen = {0}
stack = [0]
res = 0
while stack:
node = stack.pop()
for nxt, cost in g[node]:
if nxt not in seen:
seen.add(nxt)
res += cost # count the reversals needed
stack.append(nxt)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each edge is traversed once.
💾 Space Complexity
O(n) for the adjacency list.
⚠️ Interview Pitfalls & Follow-ups
- Storing only the directed edges: the traversal needs both directions with their respective costs.
- Swapping the costs: traversing along the original direction means it points away from 0 and costs 1.
- Forgetting the
seenset: the tree would be re-traversed. - Assuming the input is undirected: the roads are directed, which is what creates the cost.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.