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

Medium
Description

有 n 個城市和 n-1 條單向道路組成一棵樹。需要重新定向某些道路，使得每個城市都能到達城市 0。回傳需要改變方向的道路數量。

Example:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] Output: 3

Intuition#

從城市 0 出發 BFS/DFS，遇到順向邊（離開 0）就需要反轉。

  • 將有向圖視為無向圖來遍歷，但記錄原始方向
  • 從節點 0 出發，若邊的方向是「從 0 方向往外」，則需要反轉
  • 因為是樹結構，不需要額外的 visited 判斷（用 parent 即可）

Approaches#

1: BFS#

  • 概念: 建立雙向鄰接表，標記原始方向。從 0 開始 BFS，遇到原始方向為離開 0 的邊就計數。
  • 時間複雜度: O(n)
  • 空間複雜度: 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#

  • 概念: 同樣的思路用 DFS 實現，程式碼更簡潔
  • 時間複雜度: O(n)
  • 空間複雜度: 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: 有向樹的方向調整 – 轉為無向圖遍歷，同時追蹤原始方向
  • 關鍵技巧: 用 cost = 1（原始方向）和 cost = 0（反向）來標記邊，遍歷時直接累加 cost 即可