MediumRating 1634

1466. Reorder Routes to Make All Paths Lead to the City Zero

graphdfsbfs

解題說明

Reorder Routes to Make All Paths Lead to the City Zero

題目描述：有 n 個城市（編號 0 到 n-1）以及 n-1 條有向道路構成一棵樹。要讓所有城市都能抵達城市 0，可以改變任意道路的方向，求最少需要改變幾條道路的方向。

解題思路：建立一個無向鄰接圖，但同時記錄原始方向：對原始邊 (a→b) 建立雙向邊，但標記正向邊（a→b，權重 1）和反向邊（b→a，權重 0）。從節點 0 出發做 BFS/DFS，遍歷所有節點。若走到一條「需要反轉的邊」（即原始方向是「遠離 0」的），則計數加 1。所有邊的正向權重之和即為答案。

C++ 解法

複雜度分析

時間複雜度：O(n) — 建圖 O(n)（n-1 條邊），BFS 遍歷所有節點和邊各一次。

空間複雜度：O(n) — 鄰接表和 BFS 隊列最多儲存 O(n) 個節點。

虛擬碼

1. Build undirected adjacency list with edge weights:
   - For each edge (a, b): add (b, 1) to adj[a] and (a, 0) to adj[b]
2. BFS from node 0, mark visited
3. For each unvisited neighbor (next, cost):
   a. flips += cost
   b. Mark next as visited, enqueue
4. Return flips

其他解法

DFS 遞迴：邏輯與 BFS 完全相同，只是用遞迴 DFS 替代隊列。在 n 較大時可能有堆疊溢位風險，可改用迭代 DFS（自定義堆疊）。

換個視角：目標等價於讓所有邊方向都「指向 0」，即在以 0 為根的樹中，所有邊應從子節點指向父節點。因此計算有多少條原始邊是「從父節點指向子節點」的，就是需要翻轉的數量。兩種視角本質相同，BFS/DFS 是具體實作方式。

延伸思考

如果不是樹而是有環的有向圖，此問題是否仍有解？如何判斷？
若要讓所有節點可以從節點 0 到達（反向），翻轉策略有何不同？
如果每條道路有翻轉成本（不同邊的翻轉代價不同），應用什麼演算法求最小總成本？

Reorder Routes to Make All Paths Lead to the City Zero — CaffeCode