📘 題目敘述
有 n 個城市，編號從 0 到 n - 1。有 n - 1 條道路，把所有城市連成一棵樹。
每條道路原本都有方向，connections[i] = [a, b] 表示有一條道路從城市 a 指向城市 b。
你可以改變一些道路的方向。請回傳最少需要改變方向的道路數量，才能讓每個城市都可以沿著道路走到城市 0。
條件限制
2 <= n <= 5 * 10^4connections.length == n - 1connections[i].length == 20 <= a_i, b_i <= n - 1a_i != b_i
🧠 解題思路
我這題的想法是把原本有方向的邊，轉成「無向圖 + 額外資訊」，然後從 0 出發 DFS 一次就能算出答案。
做法是這樣：
對每條原始邊 a -> b：
- 我在
g[a]放一條到b的邊，並標記k = 0 k = 0的意思是：這條邊方向是「離開0的方向」（如果我從0的 DFS 走到它，就代表它需要被反轉）- 我在
g[b]放一條到a的邊，並標記k = 1 k = 1的意思是：這條邊方向本來就是「往0的方向」（從b走到a不需要反轉）
接著我從城市 0 做 DFS：
- 每當我走一條
k == 0的邊去拜訪沒看過的城市，代表這條原本方向是「從目前節點往外」的，若要讓大家都能走回0，就必須把它反轉，所以ans++ k == 1的邊代表原本就是朝向 DFS 起點方向，不需要反轉
因為整張圖是一棵樹，每個城市只會被走到一次，所以 DFS 過程中把所有需要反轉的邊累加起來，就是最小答案。
所有變數
g：鄰接表，g[i]存(to, k)to：相鄰城市k == 0：代表原始邊方向是i -> to（走這條邊會需要反轉）k == 1：代表原始邊方向是to -> i（走這條邊不需要反轉）visit：記錄城市是否已 DFS 走過，避免走回頭造成重複ans：需要反轉的邊數（最後回傳）
🪜 主要流程步驟
1. 建立「無向鄰接表 + 方向標記」
我把每條輸入 a -> b 同時加兩條邊：
g[a].push_back({b, 0})g[b].push_back({a, 1})
這樣我在 DFS 時永遠可以走到鄰居，但用 k 判斷「原本方向」是否要反轉。
2. 從城市 0 做 DFS，確保每個城市只走一次
我用 visit 防止重複：
- 每到一個城市
i，先visit[i] = true - 掃描
g[i]的所有鄰居(to, k) - 如果
to已走過就跳過 - 否則表示這條邊是樹上通往未拜訪子節點的邊
3. 走到未拜訪鄰居時，遇到 k==0 就代表必須反轉
當我要從 i 走到 to：
- 如果
k == 0，代表原本方向是i -> to - 但我們希望
to能走回0，這條邊應該要變成to -> i - 所以這條邊必須反轉，
ans++
然後遞迴 check(to) 繼續走下去。
4. DFS 結束後回傳 ans
因為樹的每條邊只會在 DFS 走向未訪問節點時被處理一次，所有需要反轉的邊都會被正確累加，最後回傳 ans。
⏱️ 複雜度
- 時間複雜度：
O(n)，因為是樹，邊數n-1，每個節點和邊都只會被處理一次。 - 空間複雜度：
O(n)，鄰接表g需要存2*(n-1)條邊，visit也需要n，遞迴深度最壞O(n)。
💻 程式碼實作
class Solution {
public:
vector<vector<pair<int, int>>> g; // g[0]是點 g[1]0是不動1是反
vector<bool> visit;
int ans = 0;
void check(int i) {
visit[i] = true;
for (auto [to, k] : g[i]) {
if (visit[to]) {
continue;
} else {
if (k == 0) {
ans++;
}
check(to);
}
}
}
int minReorder(int n, vector<vector<int>>& connections) {
g.assign(n, {});
visit.assign(n, false);
for (auto& x : connections) { // auto自動抓型態
int a = x[0], b = x[1];
g[a].push_back({b, 0});
g[b].push_back({a, 1});
}
check(0);
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/