有
n個城市和n-1條單向道路組成一棵樹。需要重新定向某些道路，使得每個城市都能到達城市0。回傳需要改變方向的道路數量。
Example:
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] Output: 3
Intuition
TIP
從城市 0 出發 BFS/DFS，遇到順向邊（離開 0）就需要反轉。
- 將有向圖視為無向圖來遍歷，但記錄原始方向
- 從節點 0 出發，若邊的方向是「從 0 方向往外」，則需要反轉
- 因為是樹結構，不需要額外的 visited 判斷（用 parent 即可）
Approaches
1. BFS — O(n) / O(n)
- Idea: 建立雙向鄰接表，標記原始方向。從 0 開始 BFS，遇到原始方向為離開 0 的邊就計數。
- Time:
O(n) - Space:
O(n)
class Solution {
fun minReorder(n: Int, connections: Array<IntArray>): Int {
val graph = Array(n) { mutableListOf<IntArray>() }
for ((u, v) in connections) {
graph[u].add(intArrayOf(v, 1)) // 原始方向
graph[v].add(intArrayOf(u, 0)) // 反向（不需改變）
}
val visited = BooleanArray(n)
val queue = ArrayDeque<Int>()
queue.add(0)
visited[0] = true
var count = 0
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
for ((next, cost) in graph[node]) {
if (!visited[next]) {
visited[next] = true
count += cost
queue.add(next)
}
}
}
return count
}
}⭐ 2. DFS — O(n) / O(n)
- Idea: 同樣的思路用 DFS 實現，程式碼更簡潔
- Time:
O(n) - Space:
O(n)
class Solution {
fun minReorder(n: Int, connections: Array<IntArray>): Int {
val graph = Array(n) { mutableListOf<IntArray>() }
for ((u, v) in connections) {
graph[u].add(intArrayOf(v, 1))
graph[v].add(intArrayOf(u, 0))
}
val visited = BooleanArray(n)
var count = 0
fun dfs(node: Int) {
visited[node] = true
for ((next, cost) in graph[node]) {
if (!visited[next]) {
count += cost
dfs(next)
}
}
}
dfs(0)
return count
}
}🔑 Takeaways
- Pattern: 有向樹的方向調整 — 轉為無向圖遍歷，同時追蹤原始方向
- Key trick: 用
cost = 1（原始方向）和cost = 0（反向）來標記邊，遍歷時直接累加 cost 即可