LeetCode 1466. 重新规划路线

字数 2160 2025-11-07 12:32:50

LeetCode 1466. 重新规划路线

题目描述：
有 n 个城市（编号从 0 到 n-1），以及 n-1 条连接这些城市的道路，使得任意两个城市之间只有一条路径可以互通（即这些道路构成了一棵树）。最初，这些道路是单向的，由一个数组 connections 表示，其中 connections[i] = [a_i, b_i] 表示存在一条从城市 a_i 到城市 b_i 的单向道路。

现在，我们需要重新规划一些道路的方向，使得每个城市都能到达城市 0（首都）。你可以改变任意道路的方向。题目要求计算需要改变方向的最少道路数量。

解题过程：

第一步：理解问题核心

城市和道路构成了一棵树，这意味着任意两个城市之间有且仅有一条路径。
道路最初是单向的。我们的目标是让所有城市都能通向城市 0。
我们可以改变道路的方向，每次改变计为一次操作。
问题等价于：从城市 0 出发，能“正向”到达的城市不需要改变道路方向；而为了能让其他城市到达 0，我们需要将某些指向“错误”方向的道路反转。

第二步：转换问题视角（关键）
直接思考“从某个城市如何走到城市0”可能比较绕。一个更有效的方法是进行从城市0开始的BFS（广度优先搜索）或DFS（深度优先搜索）。

我们可以将问题重新解读：

将原图中的每条有向边看作一条无向边。因为城市间本来就是连通的树，所以这样处理后的图依然是连通的。
然后，我们从城市 0 开始，遍历这棵无向树。
在遍历过程中，如果我们沿着一条无向边从城市 u 走到城市 v，但在原始的有向图中，这条边是 u -> v，那么这意味着从 0 到 v 的这条路径是“顺向”的，我们不需要改变这条边的方向。
但是，如果在原始的有向图中，这条边是 v -> u，那么当我们从 u（更靠近0）走到 v（更远离0）时，实际上我们走的方向与原始道路的方向是相反的。为了让 v 能到达 0，原始的那条 v -> u 边就需要被反转成 u -> v。所以，每遇到一条这样的“反向”边，我们的计数器就需要加1。

第三步：构建无向图并记录方向信息

我们使用邻接表来表示这棵无向树。邻接表 graph 的索引代表城市编号，每个 graph[i] 是一个列表，存储与城市 i 相邻的城市。
同时，为了在遍历时能判断边的原始方向，我们需要一个高效的方法。一个巧妙的做法是：使用一个集合（Set）来存储所有原始的有向边。但是，对于无向图的遍历，我们需要知道两个顶点之间是否存在边，而集合查找是高效的。
- 更常见的做法是：在构建无向图 graph 时，对于 connections 中的每条有向边 [a, b]，我们在 graph[a] 中添加 (b, 1)，在 graph[b] 中添加 (a, 0)。这里的 1 表示从 a 到 b 是原始的正向边，0 表示从 b 到 a 是原始的反向边（相对于从 a 到 b 的遍历而言）。这样，在遍历时，我们就能立刻知道当前经过的边在原始图中是正向还是反向。

第四步：执行BFS/DFS遍历

初始化一个队列（用于BFS）或栈（用于DFS），将起点城市 0 放入。同时，创建一个 visited 集合或数组，记录已访问过的城市，防止走回头路。将城市 0 标记为已访问。
初始化计数器 count = 0，用于记录需要反转的边数。
开始遍历：
- 从队列中取出一个城市 u。
- 遍历 u 的所有邻居 v 以及对应的方向标志 direction（就是我们之前在邻接表中存储的 1 或 0）。
- 如果邻居 v 未被访问：
  - 将其标记为已访问，并加入队列。
  - 检查 direction：
    - 如果 direction 为 1，说明我们走过的这条边在原始图中是 u -> v。这是一条背离城市 0 的边。为了让 v 能到达 0，这条边需要被反转。因此，count 需要加 1。
    - 如果 direction 为 0，说明我们走过的这条边在原始图中是 v -> u。这是一条指向城市 0 方向（或者说指向 u）的边。这条边本身就能让 v 到达 u 进而到达 0，所以不需要反转。
遍历结束后，计数器 count 的值就是我们需要的最少反转次数。

第五步：为什么这样是对的？
因为树的结构保证了从城市 0 到任何其他城市只有唯一路径。我们的BFS/DFS遍历了所有城市，并且对于每条从 0 出发通往叶节点的路径上的每一条边，我们都进行了判断。如果一条边在原始图中是背离 0 的（即从已访问节点指向未访问节点），那么它就必须被反转，否则那个未访问的节点就无法到达 0。我们统计的所有这类边的数量，就是答案。

总结：
这个算法的核心是将有向图问题转化为在无向树上的遍历问题，并通过在邻接表中存储边的方向信息，在遍历过程中动态判断哪些边需要被反转。时间复杂度为 O(n)，空间复杂度为 O(n)。

LeetCode 1466. 重新规划路线题目描述：有 n 个城市（编号从 0 到 n-1 ），以及 n-1 条连接这些城市的道路，使得任意两个城市之间只有一条路径可以互通（即这些道路构成了一棵树）。最初，这些道路是单向的，由一个数组 connections 表示，其中 connections[i] = [a_i, b_i] 表示存在一条从城市 a_i 到城市 b_i 的单向道路。现在，我们需要重新规划一些道路的方向，使得每个城市都能到达城市 0 （首都）。你可以改变任意道路的方向。题目要求计算需要改变方向的最少道路数量。解题过程：第一步：理解问题核心城市和道路构成了一棵树，这意味着任意两个城市之间有且仅有一条路径。道路最初是单向的。我们的目标是让所有城市都能通向城市 0 。我们可以改变道路的方向，每次改变计为一次操作。问题等价于：从城市 0 出发，能“正向”到达的城市不需要改变道路方向；而为了能让其他城市到达 0 ，我们需要将某些指向“错误”方向的道路反转。第二步：转换问题视角（关键）直接思考“从某个城市如何走到城市0”可能比较绕。一个更有效的方法是进行从城市0开始的BFS（广度优先搜索）或DFS（深度优先搜索）。我们可以将问题重新解读：将原图中的每条有向边看作一条无向边。因为城市间本来就是连通的树，所以这样处理后的图依然是连通的。然后，我们从城市 0 开始，遍历这棵无向树。在遍历过程中，如果我们沿着一条无向边从城市 u 走到城市 v ，但在原始的有向图中，这条边是 u -> v ，那么这意味着从 0 到 v 的这条路径是“顺向”的，我们不需要改变这条边的方向。但是，如果在原始的有向图中，这条边是 v -> u ，那么当我们从 u （更靠近0）走到 v （更远离0）时，实际上我们走的方向与原始道路的方向是相反的。为了让 v 能到达 0 ，原始的那条 v -> u 边就需要被反转成 u -> v 。所以，每遇到一条这样的“反向”边，我们的计数器就需要加1 。第三步：构建无向图并记录方向信息我们使用邻接表来表示这棵无向树。邻接表 graph 的索引代表城市编号，每个 graph[i] 是一个列表，存储与城市 i 相邻的城市。同时，为了在遍历时能判断边的原始方向，我们需要一个高效的方法。一个巧妙的做法是：使用一个集合（Set）来存储所有原始的有向边。但是，对于无向图的遍历，我们需要知道两个顶点之间是否存在边，而集合查找是高效的。更常见的做法是：在构建无向图 graph 时，对于 connections 中的每条有向边 [a, b] ，我们在 graph[a] 中添加 (b, 1) ，在 graph[b] 中添加 (a, 0) 。这里的 1 表示从 a 到 b 是原始的正向边， 0 表示从 b 到 a 是原始的反向边（相对于从 a 到 b 的遍历而言）。这样，在遍历时，我们就能立刻知道当前经过的边在原始图中是正向还是反向。第四步：执行BFS/DFS遍历初始化一个队列（用于BFS）或栈（用于DFS），将起点城市 0 放入。同时，创建一个 visited 集合或数组，记录已访问过的城市，防止走回头路。将城市 0 标记为已访问。初始化计数器 count = 0 ，用于记录需要反转的边数。开始遍历：从队列中取出一个城市 u 。遍历 u 的所有邻居 v 以及对应的方向标志 direction （就是我们之前在邻接表中存储的 1 或 0 ）。如果邻居 v 未被访问：将其标记为已访问，并加入队列。检查 direction ：如果 direction 为 1 ，说明我们走过的这条边在原始图中是 u -> v 。这是一条背离城市 0 的边。为了让 v 能到达 0 ，这条边需要被反转。因此， count 需要加 1 。如果 direction 为 0 ，说明我们走过的这条边在原始图中是 v -> u 。这是一条指向城市 0 方向（或者说指向 u ）的边。这条边本身就能让 v 到达 u 进而到达 0 ，所以不需要反转。遍历结束后，计数器 count 的值就是我们需要的最少反转次数。第五步：为什么这样是对的？因为树的结构保证了从城市 0 到任何其他城市只有唯一路径。我们的BFS/DFS遍历了所有城市，并且对于每条从 0 出发通往叶节点的路径上的每一条边，我们都进行了判断。如果一条边在原始图中是背离 0 的（即从已访问节点指向未访问节点），那么它就必须被反转，否则那个未访问的节点就无法到达 0 。我们统计的所有这类边的数量，就是答案。总结：这个算法的核心是将有向图问题转化为在无向树上的遍历问题，并通过在邻接表中存储边的方向信息，在遍历过程中动态判断哪些边需要被反转。时间复杂度为 O(n)，空间复杂度为 O(n)。