LeetCode 1466. 重新规划路线

约 6 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 LeetCode 75
标签
深度优先搜索 广度优先搜索 图

题目描述

✅ 1466. 重新规划路线

image-20260928234028752

image-20260928234028754

题意分析

原道路有方向，但忽略方向后，所有城市和道路组成一棵树。可以把某些道路反向，目标是让每个城市都能沿有向道路到达城市零，求最少需要反转多少条。

目标是其他城市走向零，并不是让零出发走到所有城市。树上任意两城之间只有一条无向路径，因此不能依赖别的绕行路线避开方向错误的道路。

解法：无向遍历配合原方向费用

核心思路

[!blue]

将城市零看作树根。每个非根城市到零的唯一路径，第一步都必须沿连接父节点的边向根走，整条路径也是不断靠近根。于是所有道路最终都必须由子节点指向父节点，正确的最终方向已经由树结构唯一确定。

从零向外遍历，可以确定每条边哪端是父、哪端是子。若原方向与当前向外移动方向相同，即父指向子，这条边必然需要反转；若原方向已经是子指向父，就不需要修改。

为了不被原方向限制而漏掉节点，邻接表要记录一条道路的两个遍历方向。对原来的 a → b，从 a 到 b 的记录费用为一，表示沿原方向向外发现新节点时需要反转；反向的 b 到 a 记录费用为零，表示实际道路已经朝向本轮父节点。这两条只是遍历记录，不是在原路网里添加两条真实道路。

用 BFS 从零搜索，每次第一次发现新节点时，把该条记录的费用累加。访问标记阻止沿反向记录回到父节点后重复计费。所有标一的边都是到根路径中不可回避的错误方向，必须反转；把它们全部反转后，每步都沿父节点前进，所有城市又都能到零，因此这个计数同时达到必要下界和合法方案。

解题步骤

  1. 建立无向邻接结构，同时为原方向记录费用一、反向遍历记录费用零。
  2. 标记城市零已访问，并放入队列。
  3. 取出一个城市，跳过已访问邻居；第一次发现的邻居先标记，再累加对应方向费用并入队。
  4. 全树遍历完后，返回累计费用，也就是最少反转数。

代码实现

class Solution {
    public int minReorder(int n, int[][] connections) {
        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];
            int b = e[1];

            // 正向边：原方向就是 a -> b
            graph.get(a).add(new int[] {
                b,
                1,
            });
            // 反向边：只为走通全树补上，不计费
            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];
                int 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
    }

    // 建无向邻接表，同时保留每条边的原始方向
    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)$，树共有 n - 1 条道路，每条建立两条记录，遍历时各检查常数次。
  • 空间复杂度：$O(n)$，用于邻接表、访问标记和队列。

关键点总结

[!green]

  • 根定为零后，所有真实道路都必须朝父节点方向，树的唯一通路给出必要性。
  • 遍历方向向外，要求的行驶方向向内，所以沿原方向向外的记录费用为一。
  • 双向邻接只为完整遍历，实际需要修改的方向由费用保存。
  • 第一次到达新节点时才计费，每条真实树边恰好决定一次。

易错点总结

[!yellow]

  • 把最终目标理解为从零到各城，会把需要反转和应保留的方向颠倒。
  • 只按原有向边存邻接，无法遍历那些道路本来朝向当前节点的相邻城市。
  • 双向记录都累加费用，会把同一条真实道路重复处理。
  • 两个遍历方向都标费用一或都标零，会丢失原道路朝向。
  • 忽略无向结构是树的前提，把这套逐边必选规则直接套到有可替代路线的一般图上。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/97071689
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！