重新规划路线

难度: Medium

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。

路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。

今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。

请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题目数据保证每个城市在重新规划路线方向后都能到达城市 0 。

示例 1：

输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
输出：3
解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。

示例 2：

输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
输出：2
解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。

示例 3：

输入：n = 3, connections = [[1,0],[2,0]]
输出：0

提示：

2 <= n <= 5 * 10^4
connections.length == n-1
connections[i].length == 2
0 <= connections[i][0], connections[i][1] <= n-1
connections[i][0] != connections[i][1]

Submission

运行时间: 74 ms

内存: 35.6 MB

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        # 建图的时候，指向的城市为正，被指向的为负
        map_ = [[] for _ in range(n)]
        for from_, to in connections:
            map_[from_].append(to)
            map_[to].append(-from_)
        ans = 0
        # 从0开始广搜，遇到正数答案就+1，遍历过的改为False
        not_visit = [True] * n
        not_visit[0] = False
        q = deque([0])
        while q:
            for j in map_[q.popleft()]:
                if not_visit[i := abs(j)]:
                    q.append(i)
                    if j > 0:
                        ans += 1
                    not_visit[i] = False
        return ans

Explain

题解的核心思路是将问题转换成一个有向图的遍历问题。首先，构建一个图来表示这些城市和它们之间的路线。在此图中，正向表示原始方向（从 a 到 b），负向表示反向（从 b 到 a）。使用广度优先搜索（BFS）从城市0开始遍历，记录并修改那些需要改变方向以到达城市0的路线。每次从队列中取出一个城市时，检查与它相连的城市，如果遇到的是正向连接（即原始方向是从当前城市指向另一城市），则计数器增加，因为我们需要改变这条路线的方向来确保所有城市都能到达城市0。通过这种方式，我们能够计算出需要改变方向的路线数量，以保证每个城市都能到达城市0。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        # 建立一个大小为n的邻接表，用于图的表示
        map_ = [[] for _ in range(n)]
        # 构建有向图，正表示正向连接，负表示反向连接
        for from_, to in connections:
            map_[from_].append(to)  # 正向连接
            map_[to].append(-from_)  # 反向连接
        ans = 0  # 用于统计需要改变方向的路线数
        # 记录节点访问状态，初始化所有节点为未访问
        not_visit = [True] * n
        not_visit[0] = False  # 城市0作为起点，标记为已访问
        # 使用队列进行BFS
        q = deque([0])
        while q:
            # 从队列中取出一个元素
            for j in map_[q.popleft()]:
                if not_visit[i := abs(j)]:  # 检查当前连接的城市是否未访问
                    q.append(i)  # 将未访问的城市加入队列
                    if j > 0:  # 如果是正向连接，需要改变方向
                        ans += 1
                    not_visit[i] = False  # 标记城市为已访问
        return ans

Explore

在此问题中，我们需要确定从任何城市到城市0的可达性，并且可能需要改变某些路线的方向。使用正负符号来表示连接的方向（正向为原始方向，负向为反向）可以帮助我们在遍历图时快速判断当前遍历到的路线是否需要改变方向以达到城市0。正值表示需要改变方向的路线，负值则表示不需要改变方向。这种表示方法简化了逻辑并减少了额外的存储需求，因为我们只需在遍历时检查符号即可决定是否增加变更方向的计数。

在广度优先搜索（BFS）中，一旦节点被访问，就表示我们已经找到了从起点（城市0）到该节点的最短路径（在无权图中）。重新考虑已访问的节点不仅是不必要的，而且会导致不必要的重复计算和可能的无限循环，增加时间复杂度。因此，跳过已访问的节点可以保证每个节点只被处理一次，确保算法效率。如果不跳过，算法可能会陷入无效操作和增加执行时间。

在这个问题的解法中，图的邻接表使用正值表示从当前节点出发到另一节点的有向边，使用负值表示从另一节点到当前节点的反向边。因此，当从队列中取出一个城市j时，我们需要确定与之相连的其他城市的索引，无论这个连接是正向还是反向。使用`abs(j)`能够从正负j中统一提取出城市索引，这简化了处理逻辑，使得我们可以在不区分正向还是反向连接的情况下，统一处理所有连接。