LeetCode 1466. 重新规划路线

2026-07-14 HGNULB 约 12 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 1466. 重新规划路线

题意分析

输入是 n 座编号 0..n-1 的城市和 n-1 条有向道路，要求的是「最少翻转多少条道路的方向，才能让每座城市都走得到城市 0」。注意题目要的不是输出方案，只要一个最小次数。

约束里藏着最关键的信号：边数恰好是 n-1，而且题目明确说这些路忽略方向后连通且无环，也就是说底层结构是一棵无根树。这一点带来两个直接结论。第一，只要把方向抹掉，从 0 出发就一定能走到全部 n 个节点，不会有走不到的孤岛。第二，树上任意两点之间的路径唯一，所以不存在「换一条路绕过去」的选择，也不用担心同一个目标被多条路径重复计算。

第二个要想透的点是：一条边最终该朝哪边，其实完全没有自由度。把 0 当作树根，那么每条边都连着一个「离 0 近的一端」和一个「离 0 远的一端」。远端的城市想到 0，唯一的路径必须经过这条边，而且必须从远端走向近端。所以每条边的最终方向被唯一确定：一律指向靠近 0 的那一头。于是问题退化成一次纯粹的统计——原方向是「远端指向近端」的边保持不动，原方向是「近端指向远端」的边必须翻转，答案就是后者的数量。既然方案唯一，它自然也就是最小的。

边界方面，n >= 2 保证至少有一条边，不存在空图；connections[i][0] != connections[i][1] 保证没有自环；节点 0 本身不需要付任何代价。真正容易翻车的地方不是边界数据，而是「近端 / 远端」这个判断必须以 0 为参照点，不能凭编号大小或输入顺序去猜。

解法：无向建图 + 方向标记后从 0 出发 BFS

核心思路

先说为什么必须建无向图。如果只按原方向建邻接表，从 0 出发只能顺着出边走。而 0 的出边在题目里是要被翻转掉的那一类，最极端的情况是所有边都指向 0（答案为 0），此时 0 一条出边都没有，遍历第一步就停住，连其余 n-1 个节点长什么样都看不到。反过来，只有把每条边同时登记成 a -> b 和 b -> a，遍历才能沿着树自由铺开、覆盖全部节点。

但抹掉方向会丢掉计数所需的信息，所以要在补边的同时给每条有向记录打一个标记：原始给出的 a -> b 记为「正向」，权 1；为了走通全树而补出来的 b -> a 记为「反向」，权 0。这样一条无向边在邻接表里出现两次，两次的权刚好互补，遍历时从哪一头进入，就自然读到对应的那一份权。

接下来是正确性的关键。从 0 出发做遍历（BFS 或 DFS 都行），第一次访问某个节点 next 时，是从某个已访问节点 cur 走过去的。不变量：遍历中每一次「cur -> next」的移动，cur 到 0 的树上距离一定严格小于 next 到 0 的树上距离。 在树上这个不变量是自动成立的，因为 0 到 next 的唯一路径必然经过 next 的父节点，而遍历里第一次触达 next 的那个 cur 就是它的父节点。

有了这个不变量，判定就变得极其局部：既然 cur 是近端、next 是远端，那么边 (cur, next) 的最终方向必须是 next -> cur。如果我们此刻读到的权是 1，说明原方向恰好是 cur -> next，与「行进方向」同向，也就是背离 0，必须翻转，计数加一；如果读到的权是 0，说明原方向本来就是 next -> cur，已经朝着 0，白拿。所以「沿远离 0 的方向走，遇到与行进方向同向的原始边就必须翻转」这句话是不变量的直接推论，而不是某种巧合。

最后，每条边在遍历中恰好被判定一次（第二次从远端回望近端时，近端已访问，直接跳过），所以累加出来的就是需要翻转的边数总量，一趟遍历即得答案，无需任何搜索或回溯。

解题步骤

建一个长度为 n 的邻接表，每个元素存 (邻居, 权) 二元组。为什么：既要能双向走，又要保留原方向信息，二元组是最省事的载体。

遍历 connections，对每条 [a, b] 往 graph[a] 塞 (b, 1)、往 graph[b] 塞 (a, 0)。为什么：1 标记「顺着这个方向走等于背离原始箭头的目的地」即需翻转，0 标记「这条记录是补出来的虚拟边，走它不花钱」。

准备 visited 数组和队列，把 0 标记为已访问并入队，答案计数置 0。为什么：0 是唯一的参照根，也是唯一不需要付费的起点；起点必须立刻标记，否则它会被邻居当成新节点再算一遍入边。

循环出队 cur，扫描 graph[cur] 的每条记录 (next, cost)。为什么：出队顺序不重要，重要的只是「第一次访问」这个时刻，BFS 与 DFS 在本题给出完全相同的答案。

若 next 已访问就跳过；否则立刻标记 next 已访问、ans += cost、把 next 入队。为什么：跳过的那些正是「回望父节点」的记录，它们的权不该被计入；而入队时就标记可以防止同一节点从多个方向被重复展开。

队列耗尽后返回 ans。为什么：树连通，队列空即代表全部 n 个节点都已判定完毕，每条边都被恰好统计过一次。

以 n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] 走一遍。先建表：[0,1] 让 graph[0] 得到 (1,1)、graph[1] 得到 (0,0)；[1,3] 让 graph[1] 得到 (3,1)、graph[3] 得到 (1,0)；[2,3] 让 graph[2] 得到 (3,1)、graph[3] 得到 (2,0)；[4,0] 让 graph[4] 得到 (0,1)、graph[0] 得到 (4,0)；[4,5] 让 graph[4] 得到 (5,1)、graph[5] 得到 (4,0)。最终 graph[0] = [(1,1),(4,0)]，graph[1] = [(0,0),(3,1)]，graph[2] = [(3,1)]，graph[3] = [(1,0),(2,0)]，graph[4] = [(0,1),(5,1)]，graph[5] = [(4,0)]。

遍历过程如下。出队 0：看到 (1,1)，1 未访问，ans = 1，入队 1；看到 (4,0)，4 未访问，ans 仍为 1，入队 4。出队 1：(0,0) 中 0 已访问，跳过；(3,1) 中 3 未访问，ans = 2，入队 3。出队 4：(0,1) 中 0 已访问，跳过（这一步很关键，若不跳过就会多算 1）；(5,1) 中 5 未访问，ans = 3，入队 5。出队 3：(1,0) 已访问跳过；(2,0) 中 2 未访问，权为 0，ans 仍为 3，入队 2。出队 5：(4,0) 已访问跳过。出队 2：(3,1) 中 3 已访问，跳过。

访问顺序是 0 -> 1 -> 4 -> 3 -> 5 -> 2，逐条边结算：边 0 -> 1 与行进方向 0 到 1 同向，计数；边 4 -> 0 与行进方向 0 到 4 反向，不计；边 1 -> 3 与行进方向 1 到 3 同向，计数；边 4 -> 5 与行进方向 4 到 5 同向，计数；边 2 -> 3 与行进方向 3 到 2 反向，不计。三条计数，返回 3，与预期一致。

代码实现

class Solution {
    public int minReorder(int n, int[][] connections) {
        // 建无向邻接表：cost = 1 表示这条边的原方向是「从 0 向外」，走到它时必须翻转
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] e : connections) {
            int a = e[0], b = e[1];
            graph.get(a).add(new int[] {b, 1}); // 正向边：原方向就是 a -> b
            graph.get(b).add(new int[] {a, 0}); // 反向边：只为走通全树补上，不计费
        }

        int ans = 0;
        boolean[] visited = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>();
        visited[0] = true;
        queue.offer(0);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int[] e : graph.get(cur)) {
                int next = e[0], cost = e[1];
                if (visited[next]) {
                    continue;
                }
                // cur 一定比 next 更靠近 0，这条边最终必须指向 cur
                visited[next] = true;
                ans += cost;
                queue.offer(next);
            }
        }
        return ans;
    }
}

func minReorder(n int, connections [][]int) int {
    type edge struct {
        to   int
        cost int // 1 表示原方向是「从 0 向外」，走到它时必须翻转
    }

    // 建无向邻接表，同时保留每条边的原始方向
    graph := make([][]edge, n)
    for _, e := range connections {
        a, b := e[0], e[1]
        graph[a] = append(graph[a], edge{to: b, cost: 1}) // 正向边
        graph[b] = append(graph[b], edge{to: a, cost: 0}) // 反向边，只为走通全树
    }

    ans := 0
    visited := make([]bool, n)
    visited[0] = true
    queue := []int{0}

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        for _, e := range graph[cur] {
            if visited[e.to] {
                continue
            }
            // cur 一定比 e.to 更靠近 0，所以这条边最终必须指向 cur
            visited[e.to] = true
            ans += e.cost
            queue = append(queue, e.to)
        }
    }
    return ans
}

复杂度分析

时间复杂度：$O(n)$。建表遍历 connections 一次，共 n-1 条边、产生 2(n-1) 条邻接记录；BFS 每个节点恰好出队一次，每条邻接记录恰好被扫描一次，所以总工作量与 $n$ 成正比。

空间复杂度：$O(n)$。邻接表存 2(n-1) 条记录，visited 数组占 n，队列最多同时容纳 $O(n)$ 个节点（星形树的第一层就能撑满）。

关键点总结

「让所有点到达某个指定点」的问题，先把那个点当根。一旦确定根，树上每条边的「近端 / 远端」就固定了，很多看似需要搜索的选择会立刻退化成一次线性统计。

有向图上要做全局遍历时，敢于建无向图，但把方向信息降级成边权而不是丢掉。这是一个通用手法：结构性质（连通、可遍历）用无向图保证，语义性质（方向、代价）用权或标记携带，两者互不干扰。

树上「任意两点路径唯一」是一个极强的前提，它同时消灭了「重复计数」和「需要在多方案里取最优」两类麻烦。看到 n 个点 n-1 条边且连通，先把这个结论用上。

判定条件要设计成只依赖遍历时的局部状态。本题的判定只看「当前这条邻接记录的权」，靠的是一条全局不变量（cur 比 next 更靠近根）在背后兜底。写出不变量，局部判定的正确性才有依据。

迭代遍历比递归更抗极端形状。本题 n 可达 5 * 10^4，退化成一条链时递归深度就是 5 万，实测在 Java 默认栈上会抛 StackOverflowError；显式队列的写法在同一输入下 9ms 出结果。

面试视角：面试官期望你开口先说两句话——「忽略方向后是一棵树」和「以 0 为根后每条边的最终方向唯一确定」，把问题降成计数，再谈怎么建图。常见追问有三个方向：一是「如果不是树而是一般有向图呢」，此时每条边的方向不再唯一确定（一个点可能有多条到 0 的候选路径），最少翻转数变成在「反向边代价 1、正向边代价 0」的图上求每个点到 0 的最短路，或反过来看成从 0 出发的 0-1 BFS 单源问题，且答案不再是简单求和；二是「能不能不建图」，可以答用并查集或按输入顺序处理都不行，因为需要的是相对 0 的层级关系；三是「递归会不会爆栈」，直接给出上面那条链的反例。

易错点总结

只按原方向建有向邻接表：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] → 从 0 只能顺出边走出 0 -> 1 -> 3，实跑仅访问到 3 个节点、返回 2（正确答案 3）；换成全部指向 0 的链 n = 6, connections = [[1,0],[2,1],[3,2],[4,3],[5,4]]，0 一条出边都没有，只访问到 1 个节点、返回 0（这组恰好答案也是 0，属于「错了却过了」的假象）。

正反方向的权标记写反了（正向记 0、反向记 1）：n = 3, connections = [[1,0],[2,0]] → 实跑返回 2（正确 0）；n = 5, connections = [[0,1],[0,2],[0,3],[0,4]] → 实跑返回 0（正确 4）。特别阴的是 n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] 这组标记反了也仍然返回 2，官方样例二根本测不出来，必须自己补星形用例。

把 ans += cost 写在 visited 判断之前：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] → 实跑返回 5（正确 3）。原因是每条无向边的两份记录都被累加，正反权之和恒为 1，结果永远等于 n - 1（该用例即 5，n = 5 的用例返回 4，n = 3 的用例返回 2），一眼看不出规律但一定错。

忘记在入队前把起点 0 标记为已访问：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] → 实跑返回 3（正确 2）；n = 3, connections = [[1,0],[2,0]] → 实跑返回 1（正确 0）。0 会被它的邻居当成一个未访问的新节点再结算一次入边，多算的量取决于第一个邻居那条边的方向。

在无向邻接表上遍历却完全不做 visited 或父节点判断：任意 n >= 2 的输入（哪怕 n = 2, connections = [[0,1]]）→ 0 和 1 会互相无限递归，实跑立刻抛 StackOverflowError；换成 BFS 则是队列无限增长直到内存耗尽。

用递归 DFS 却不考虑链式退化：n = 50000 且 connections = [[0,1],[1,2],...,[49998,49999]] → 递归深度 5 万，实跑在 Java 默认栈上抛 StackOverflowError；同一输入换成显式队列的迭代写法 9ms 返回 49999。

参照点选错，从别的节点出发遍历：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] 若从 1 开始 BFS → 实跑返回 2（正确 3）。「近端 / 远端」只对 0 有意义，换个根就等于在解另一道题。

误以为要真的枚举翻转方案再验证可达性：n 上限是 5 * 10^4，边数 n - 1，枚举翻转子集是 $O(2^{n-1})$ 量级，n 稍大就必然超时。这里没有任何需要搜索的自由度——每条边的最终方向被 0 唯一决定，只需数一遍。

把 connections[i][0] 默认当成 connections[i][1] 的父节点：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] 里 [3,2] 的 3 其实是 2 的子节点（以 0 为根时层级是 0 - 1 - 2 - 3 - 4）。输入既不保证按层序给出，也不保证第一个数更靠近 0，必须靠遍历自己算出层级关系。

相似题目

题目	难度	考察点
841. 钥匙和房间	中等	同样是从 0 出发的有向图可达性，但方向不可修改、只需判断能否走遍，不必补反向边也不必累加代价
997. 找到小镇的法官	简单	也靠边的方向解题，但只用统计每个点的入度与出度即可，无需任何遍历，是「方向信息可局部聚合」的对照
310. 最小高度树	中等	同为无向树上的全局问题，但根不是给定的而是要求出来，做法从一次定根遍历变成按度数逐层剥叶
547. 省份数量	中等	无向图但不保证连通，重点是数连通块个数，需要对每个未访问点各起一次遍历，而本题从 0 一趟走完