## [重新規劃路線](https://leetcode-cn.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/) #### 思路 題目里面已經給了我們一些提示，所有的路徑形成樹。對于樹來說無非是BFS&DFS。先不管，還是先分析題目 * 兩點之間只有一條路線 → 相鄰的節點形成樹（不管方向） * 要求修改之后所有的點都能走向0節點，那自然可以想到以0作為樹的根的話，所有節點的方向都要指向根，要是沒有指向上面，就要修改他的方向 ``` 示例: [[0,1],[1,3],[2,3],[4,0],[4,5]] 0 ↙ ↖ 1 4 ↙ ↘ 3 5 ↗ 2 向下指的箭頭，需要修改方向， result = 3 ``` BFS,DFS 這道題應該都可以AC，這邊嘗試BFS。 實際做的過程中，TLE。 主要問題在于BFS遍歷下一層時，遍歷數組并找到包含下一層的路徑，且將該路徑記錄為visited，下次遍歷時需要判斷路徑在不在visited中的路徑。其中python的`in`操作太多，增加了時間復雜度。 **改進代碼及思路**，進行BFS前，先構建一個鄰接表。BFS時對鄰接表進行遍歷。 #### 代碼 python3 ``` class Solution: def minReorder(self, n: int, connections: List[List[int]]) -> int: routes = {} for i,o in connections: routes[i] = routes.get(i,[]) + [(o, 1)] routes[o] = routes.get(o,[]) + [(i, 0)] print(routes) queue = [0] visited = set([0]) result = 0 while len(queue): node = queue[0] del queue[0] for n,d in routes[node]: if n in visited: continue result += d queue.append(n) visited.add(n) return result ```