給定一個無向圖的鄰接表
graph，判斷該圖是否為二部圖（Bipartite）。即能否將所有節點分成兩組，使得每條邊的兩端分屬不同組。
Example:
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]] Output: false
Intuition
TIP
嘗試用兩種顏色著色，若能成功則是二部圖，否則不是。
- 二部圖等價於圖可以被二著色
- 用 BFS/DFS 對節點交替著色
- 若發現相鄰節點顏色相同，則不是二部圖
Approaches
1. BFS Coloring — O(V + E) / O(V)
- Idea: BFS 遍歷，交替分配顏色，發現衝突即回傳 false
- Time:
O(V + E) - Space:
O(V)
class Solution {
fun isBipartite(graph: Array<IntArray>): Boolean {
val n = graph.size
val color = IntArray(n) // 0: 未著色, 1: 組A, -1: 組B
for (start in 0 until n) {
if (color[start] != 0) continue
val queue = ArrayDeque<Int>()
queue.add(start)
color[start] = 1
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
for (next in graph[node]) {
if (color[next] == 0) {
color[next] = -color[node]
queue.add(next)
} else if (color[next] == color[node]) {
return false
}
}
}
}
return true
}
}⭐ 2. DFS Coloring — O(V + E) / O(V)
- Idea: DFS 遞迴著色，程式碼更簡潔
- Time:
O(V + E) - Space:
O(V)
class Solution {
fun isBipartite(graph: Array<IntArray>): Boolean {
val color = IntArray(graph.size)
fun dfs(node: Int, c: Int): Boolean {
color[node] = c
for (next in graph[node]) {
if (color[next] == c) return false
if (color[next] == 0 && !dfs(next, -c)) return false
}
return true
}
for (i in graph.indices) {
if (color[i] == 0 && !dfs(i, 1)) return false
}
return true
}
}🔑 Takeaways
- Pattern: 圖的二著色 — 判斷二部圖等價於圖可以被二著色
- Key trick: 圖可能不連通，需要對每個連通分量都做檢查；用
1和-1表示兩種顏色方便取反