題目
(https://leetcode-cn.com/problems/is-graph-bipartite/)
給定一個無向圖graph，當這個圖為二分圖時返回true捞蚂。
如果我們能將一個圖的節(jié)點集合分割成兩個獨立的子集A和B妇押，并使圖中的每一條邊的兩個節(jié)點一個來自A集合，一個來自B集合姓迅，我們就將這個圖稱為二分圖敲霍。
graph將會以鄰接表方式給出，graph[i]表示圖中與節(jié)點i相連的所有節(jié)點丁存。每個節(jié)點都是一個在0到graph.length-1之間的整數(shù)肩杈。這圖中沒有自環(huán)和平行邊： graph[i] 中不存在i，并且graph[i]中沒有重復的值解寝。
示例 1:
輸入: [[1,3], [0,2], [1,3], [0,2]]
輸出: true
解釋:
無向圖如下:
0----1
| |
| |
3----2
我們可以將節(jié)點分成兩組: {0, 2} 和 {1, 3}扩然。
示例 2:
輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]
輸出: false
解釋:
無向圖如下:
0----1
| \ |
| \ |
3----2
我們不能將節(jié)點分割成兩個獨立的子集。
注意:
graph 的長度范圍為 [1, 100]聋伦。
graph[i] 中的元素的范圍為 [0, graph.length - 1]夫偶。
graph[i] 不會包含 i 或者有重復的值。
圖是無向的: 如果j 在 graph[i]里邊, 那么 i 也會在 graph[j]里邊嘉抓。
分析
假設 0: 未上色, 1: 紅色, -1: 黑色
實際上就是一個上色問題, 依次判斷每個節(jié)點(防止非連通圖中有未訪問的節(jié)點),
如果未被上色則選擇一種顏色對其上色并dfs的對其鄰接點上相反的顏色, 如果鄰
接點已有相同的顏色說明上色失敗返回false,
代碼
class Solution {
public boolean isBipartite(int[][] graph) {
int[] colors = new int[graph.length];
//遍歷節(jié)點
for(int i = 0; i < graph.length; ++i){
if(colors[i] == 0 && !coloring(graph, colors, 1, i)){
return false;
}
}
return true;
}
private boolean coloring(int[][] graph, int[] colors, int color, int node) {
// 如果已上色判斷顏色是否一致, 不一致說明上色失敗
if(colors[node] != 0){
return colors[node] == color;
}
colors[node] = color;
//對節(jié)點內(nèi)的每一個值進行遍歷索守≡我ぃ看是否上色不一致
for(int next : graph[node]){
if(!coloring(graph, colors, -color, next)){
return false;
}
}
return true;
}
}
結(jié)果
