有一個有向圖，邊分為紅色和藍色。從節點
0出發，找到到每個節點的最短交替顏色路徑長度（紅藍交替）。若無法到達回傳-1。
Example:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = [] Output: [0,1,-1]
Intuition
TIP
BFS 時狀態為 (節點, 上一條邊的顏色)，確保交替顏色。
- 起點可以走紅邊也可以走藍邊，所以起點有兩個初始狀態
- 每步只能走與上一步不同顏色的邊
- 答案取兩種起始狀態到達同一節點的最小值
Approaches
⭐ 1. BFS (two states) — O(V + E) / O(V + E)
- Idea: 狀態為
(node, color)，從起點的兩種顏色同時開始 BFS - Time:
O(V + E) - Space:
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 (Level-order) — O(V + E) / O(V + E)
- Idea: 用層序 BFS 搭配 visited 陣列
- Time:
O(V + E) - Space:
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 — 狀態包含節點和邊的顏色
- Key trick: 將
(node, color)視為圖的節點做 BFS；起點需要同時加入兩種顏色的狀態