⚡Flashcard Drill➔
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

  1. Root the tree at city 0 and traverse it.
  2. 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.
  3. So store, for each undirected edge, the cost of traversing it in each direction (0 or 1).
  4. 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 seen set: 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems