leetcode：1466. 重新规划路线【图 + 脑经急转弯】

分析

首先只有n - 1个边，每条边只能转方向
那么我们从0开始出发，进行dfs
如果遇到一条正着遍历的边，我们就要让它反过来
让它指向0这一侧
（通过样例得出简单的规律）

ac code

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        # 从0开始dfs找规律
        # 把顺着路径下的顺向边全部计入
        ans = 0
        visited = [False] * n
        undirect = defaultdict(list)
        for x, y in connections:
            undirect[x].append(y)
            undirect[y].append(x)
        direct = defaultdict(set)
        for x, y in connections:
            direct[x].add(y)
        
        def dfs(now):
            nonlocal ans
            visited[now] = True
            for next in undirect[now]:
                if visited[next] is False:
                    if next in direct[now]:
                        ans += 1
                    visited[next] = True
                    dfs(next)
        
        dfs(0)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

图的问题也是可以找规律
把有向边变成无向进行dfs
然后找到所有正着的边要反过来即可