LeetCode 1466: Reorder Routes to Make All Paths Lead to the City Zero (Tree Traversal + Edge Orientation Cost)
LeetCode 1466GraphDFS/BFSToday we solve LeetCode 1466 - Reorder Routes to Make All Paths Lead to the City Zero.
Source: https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/
English
Problem Summary
We have n cities and n-1 directed roads forming a tree in undirected sense. Return the minimum number of road directions to reverse so every city can reach city 0.
Key Insight
Treat each original directed edge a -> b as two traversal choices in an undirected graph: going from a to b costs 1 reversal, and from b to a costs 0. Traversing once from city 0 and summing costs gives the minimum.
Algorithm
Build adjacency with cost labels, then BFS/DFS from node 0.
Whenever we visit an unvisited neighbor, add its edge cost and continue traversal.
Complexity Analysis
Time: O(n), each edge processed at most twice.
Space: O(n) for graph and visited array.
Common Pitfalls
- Trying to run shortest path algorithms; this is a tree, simple traversal is enough.
- Forgetting to add reverse adjacency edges with zero cost.
- Missing visited checks and counting edges repeatedly.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int minReorder(int n, int[][] connections) {
List<int[]>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : connections) {
int a = e[0], b = e[1];
g[a].add(new int[]{b, 1}); // original edge a -> b, reversing needed if traversed from 0 side
g[b].add(new int[]{a, 0}); // virtual reverse edge, no cost
}
int ans = 0;
boolean[] vis = new boolean[n];
Deque<Integer> dq = new ArrayDeque<>();
dq.offer(0);
vis[0] = true;
while (!dq.isEmpty()) {
int u = dq.poll();
for (int[] nxt : g[u]) {
int v = nxt[0], cost = nxt[1];
if (vis[v]) continue;
ans += cost;
vis[v] = true;
dq.offer(v);
}
}
return ans;
}
}func minReorder(n int, connections [][]int) int {
g := make([][][2]int, n)
for _, e := range connections {
a, b := e[0], e[1]
g[a] = append(g[a], [2]int{b, 1})
g[b] = append(g[b], [2]int{a, 0})
}
vis := make([]bool, n)
q := []int{0}
vis[0] = true
ans := 0
for len(q) > 0 {
u := q[0]
q = q[1:]
for _, p := range g[u] {
v, cost := p[0], p[1]
if vis[v] {
continue
}
ans += cost
vis[v] = true
q = append(q, v)
}
}
return ans
}class Solution {
public:
int minReorder(int n, vector<vector<int>>& connections) {
vector<vector<pair<int,int>>> g(n);
for (auto& e : connections) {
int a = e[0], b = e[1];
g[a].push_back({b, 1});
g[b].push_back({a, 0});
}
vector<int> vis(n, 0);
queue<int> q;
q.push(0);
vis[0] = 1;
int ans = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& [v, cost] : g[u]) {
if (vis[v]) continue;
ans += cost;
vis[v] = 1;
q.push(v);
}
}
return ans;
}
};from collections import deque
from typing import List
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for a, b in connections:
g[a].append((b, 1))
g[b].append((a, 0))
vis = [False] * n
q = deque([0])
vis[0] = True
ans = 0
while q:
u = q.popleft()
for v, cost in g[u]:
if vis[v]:
continue
ans += cost
vis[v] = True
q.append(v)
return ansvar minReorder = function(n, connections) {
const g = Array.from({ length: n }, () => []);
for (const [a, b] of connections) {
g[a].push([b, 1]);
g[b].push([a, 0]);
}
const vis = new Array(n).fill(false);
const q = [0];
vis[0] = true;
let ans = 0;
while (q.length) {
const u = q.shift();
for (const [v, cost] of g[u]) {
if (vis[v]) continue;
ans += cost;
vis[v] = true;
q.push(v);
}
}
return ans;
};中文
题目概述
给定 n 个城市和 n-1 条有向道路（无向意义下构成一棵树），要求最少反转多少条边，才能让所有城市都能到达城市 0。
核心思路
把每条原始有向边 a -> b 拆成无向图中的两条可走边：a -> b 代价为 1（表示需要反转），b -> a 代价为 0（方向已正确）。从 0 出发遍历整棵树，累计代价就是最小反转次数。
算法步骤
先建带代价的邻接表，再从 0 做 BFS/DFS。
每次访问未访问过的邻居时，将对应代价加入答案并继续遍历。
复杂度分析
时间复杂度：O(n)，每条边最多处理两次。
空间复杂度：O(n)，用于图和 visited 数组。
常见陷阱
- 误用最短路算法，这里是树结构，一次遍历即可。
- 忘记补反向零代价边，导致计数偏大。
- 没有 visited 判断，重复计数同一条边。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int minReorder(int n, int[][] connections) {
List<int[]>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : connections) {
int a = e[0], b = e[1];
g[a].add(new int[]{b, 1}); // original edge a -> b, reversing needed if traversed from 0 side
g[b].add(new int[]{a, 0}); // virtual reverse edge, no cost
}
int ans = 0;
boolean[] vis = new boolean[n];
Deque<Integer> dq = new ArrayDeque<>();
dq.offer(0);
vis[0] = true;
while (!dq.isEmpty()) {
int u = dq.poll();
for (int[] nxt : g[u]) {
int v = nxt[0], cost = nxt[1];
if (vis[v]) continue;
ans += cost;
vis[v] = true;
dq.offer(v);
}
}
return ans;
}
}func minReorder(n int, connections [][]int) int {
g := make([][][2]int, n)
for _, e := range connections {
a, b := e[0], e[1]
g[a] = append(g[a], [2]int{b, 1})
g[b] = append(g[b], [2]int{a, 0})
}
vis := make([]bool, n)
q := []int{0}
vis[0] = true
ans := 0
for len(q) > 0 {
u := q[0]
q = q[1:]
for _, p := range g[u] {
v, cost := p[0], p[1]
if vis[v] {
continue
}
ans += cost
vis[v] = true
q = append(q, v)
}
}
return ans
}class Solution {
public:
int minReorder(int n, vector<vector<int>>& connections) {
vector<vector<pair<int,int>>> g(n);
for (auto& e : connections) {
int a = e[0], b = e[1];
g[a].push_back({b, 1});
g[b].push_back({a, 0});
}
vector<int> vis(n, 0);
queue<int> q;
q.push(0);
vis[0] = 1;
int ans = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& [v, cost] : g[u]) {
if (vis[v]) continue;
ans += cost;
vis[v] = 1;
q.push(v);
}
}
return ans;
}
};from collections import deque
from typing import List
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for a, b in connections:
g[a].append((b, 1))
g[b].append((a, 0))
vis = [False] * n
q = deque([0])
vis[0] = True
ans = 0
while q:
u = q.popleft()
for v, cost in g[u]:
if vis[v]:
continue
ans += cost
vis[v] = True
q.append(v)
return ansvar minReorder = function(n, connections) {
const g = Array.from({ length: n }, () => []);
for (const [a, b] of connections) {
g[a].push([b, 1]);
g[b].push([a, 0]);
}
const vis = new Array(n).fill(false);
const q = [0];
vis[0] = true;
let ans = 0;
while (q.length) {
const u = q.shift();
for (const [v, cost] of g[u]) {
if (vis[v]) continue;
ans += cost;
vis[v] = true;
q.push(v);
}
}
return ans;
};
Comments