1466.重新规划路线

链接：1466.重新规划路线
难度：Medium
标签：深度优先搜索、广度优先搜索、图
简介：请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题解 1 - python

• 编辑时间：2023-12-07
• 执行用时：272ms
• 内存消耗：36.8MB
• 编程语言：python
• 解法介绍：从0点开始向外bfs。

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        froms = [[] for _ in range(n)]
        tos = [[] for _ in range(n)]
        for a, b in connections:
            froms[a].append(b)
            tos[b].append(a)
        q = deque()
        q.append((0, 0, -1))
        ans = 0
        while q:
            cur, f, p = q.popleft()
            ans += len(froms[cur]) - f
            for next in froms[cur]:
                if next != p: q.append((next, 0, cur))
            for next in tos[cur]:
                if next != p: q.append((next, 1, cur))
        return ans