1466. 重新规划路线 · Algorithm Lab

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]

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


class Solution(object):
    def minReorder(self, n, connections):
        # 构建邻接表，存储 (邻居, 是否需要反向)
        adj = [[] for _ in range(n)]
        for a, b in connections:
            adj[a].append((b, 1))  # 原方向a→b，需要反向（计数+1）
            adj[b].append((a, 0))  # 反向b→a，不需要反向
        
        visited = [False] * n
        self.res = 0  # 记录需要反向的数量
        
        # DFS遍历
        def dfs(node):
            visited[node] = True
            for neighbor, need_reverse in adj[node]:
                if not visited[neighbor]:
                    self.res += need_reverse  # 需要反向则计数+1
                    dfs(neighbor)
        
        dfs(0)  # 从0出发遍历
        return self.res
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: int
        """