1129. Shortest Path with Alternating Colors

Medium
Description

有一個有向圖，邊分為紅色和藍色。從節點 0 出發，找到到每個節點的最短交替顏色路徑長度（紅藍交替）。若無法到達回傳 -1。

Example:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = [] Output: [0,1,-1]

Intuition#

BFS 時狀態為 (節點, 上一條邊的顏色)，確保交替顏色。

  • 起點可以走紅邊也可以走藍邊，所以起點有兩個初始狀態
  • 每步只能走與上一步不同顏色的邊
  • 答案取兩種起始狀態到達同一節點的最小值

Approaches#

⭐1: BFS（雙狀態）#

  • 概念: 狀態為 (node, color)，從起點的兩種顏色同時開始 BFS
  • 時間複雜度: O(V + E)
  • 空間複雜度: O(V + E)
class Solution {
    fun shortestAlternatingPaths(n: Int, redEdges: Array<IntArray>, blueEdges: Array<IntArray>): IntArray {
        // graph[color][node] = list of neighbors, 0=red, 1=blue
        val graph = Array(2) { Array(n) { mutableListOf<Int>() } }
        for ((u, v) in redEdges) graph[0][u].add(v)
        for ((u, v) in blueEdges) graph[1][u].add(v)

        // dist[node][color]
        val dist = Array(n) { IntArray(2) { Int.MAX_VALUE } }
        val queue = ArrayDeque<IntArray>()

        // 起點：可以從紅色或藍色開始
        dist[0][0] = 0
        dist[0][1] = 0
        queue.add(intArrayOf(0, 0))  // node 0, 上一步是紅色 -> 下一步走藍色
        queue.add(intArrayOf(0, 1))  // node 0, 上一步是藍色 -> 下一步走紅色

        while (queue.isNotEmpty()) {
            val (node, color) = queue.removeFirst()
            val nextColor = 1 - color
            for (next in graph[nextColor][node]) {
                if (dist[node][color] + 1 < dist[next][nextColor]) {
                    dist[next][nextColor] = dist[node][color] + 1
                    queue.add(intArrayOf(next, nextColor))
                }
            }
        }

        return IntArray(n) { i ->
            val minD = minOf(dist[i][0], dist[i][1])
            if (minD == Int.MAX_VALUE) -1 else minD
        }
    }
}

2: BFS（層序遍歷）#

  • 概念: 用層序 BFS 搭配 visited 陣列
  • 時間複雜度: O(V + E)
  • 空間複雜度: O(V + E)
class Solution {
    fun shortestAlternatingPaths(n: Int, redEdges: Array<IntArray>, blueEdges: Array<IntArray>): IntArray {
        val graph = Array(2) { Array(n) { mutableListOf<Int>() } }
        for ((u, v) in redEdges) graph[0][u].add(v)
        for ((u, v) in blueEdges) graph[1][u].add(v)

        val result = IntArray(n) { -1 }
        val visited = Array(n) { BooleanArray(2) }
        val queue = ArrayDeque<IntArray>()

        queue.add(intArrayOf(0, 0))
        queue.add(intArrayOf(0, 1))
        visited[0][0] = true
        visited[0][1] = true
        result[0] = 0
        var steps = 0

        while (queue.isNotEmpty()) {
            steps++
            repeat(queue.size) {
                val (node, color) = queue.removeFirst()
                val nextColor = 1 - color
                for (next in graph[nextColor][node]) {
                    if (!visited[next][nextColor]) {
                        visited[next][nextColor] = true
                        if (result[next] == -1) result[next] = steps
                        queue.add(intArrayOf(next, nextColor))
                    }
                }
            }
        }
        return result
    }
}

🔑 Takeaways#

  • Pattern: 帶狀態的 BFS – 狀態包含節點和邊的顏色
  • 關鍵技巧: 將 (node, color) 視為圖的節點做 BFS；起點需要同時加入兩種顏色的狀態