題目
描述
給定一個(gè)無向圖graph悠瞬，當(dāng)這個(gè)圖為二分圖時(shí)返回true懈万。
如果我們能將一個(gè)圖的節(jié)點(diǎn)集合分割成兩個(gè)獨(dú)立的子集A和B，并使圖中的每一條邊的兩個(gè)節(jié)點(diǎn)一個(gè)來自A集合，一個(gè)來自B集合帝璧，我們就將這個(gè)圖稱為二分圖先誉。
graph將會(huì)以鄰接表方式給出，graph[i]表示圖中與節(jié)點(diǎn)i相連的所有節(jié)點(diǎn)的烁。每個(gè)節(jié)點(diǎn)都是一個(gè)在0到graph.length-1之間的整數(shù)褐耳。這圖中沒有自環(huán)和平行邊： graph[i] 中不存在i，并且graph[i]中沒有重復(fù)的值渴庆。
示例 1:
輸入: [[1,3], [0,2], [1,3], [0,2]]
輸出: true
解釋:
無向圖如下:
0----1
| |
| |
3----2
我們可以將節(jié)點(diǎn)分成兩組: {0, 2} 和 {1, 3}铃芦。
示例 2:
輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]
輸出: false
解釋:
無向圖如下:
0----1
| \ |
| \ |
3----2
我們不能將節(jié)點(diǎn)分割成兩個(gè)獨(dú)立的子集。
注意
graph 的長(zhǎng)度范圍為 [1, 100]襟雷。
graph[i] 中的元素的范圍為 [0, graph.length - 1]刃滓。
graph[i] 不會(huì)包含 i 或者有重復(fù)的值。
圖是無向的: 如果j 在 graph[i]里邊, 那么 i 也會(huì)在 graph[j]里邊耸弄。
題解
染色問題注盈，對(duì)第一個(gè)點(diǎn)染色，然后對(duì)第一個(gè)點(diǎn)的連接的點(diǎn) 染對(duì)稱色叙赚，接下去對(duì)點(diǎn)的連接的點(diǎn)繼續(xù)染色老客，當(dāng)遇到已經(jīng)染色的點(diǎn)并且顏色相同返回false結(jié)束程序
代碼
class lc785 {
int[][] map;
int[] colors;
public boolean isBipartite(int[][] graph) {
colors = new int[graph.length];
boolean flag = true;
map = graph;
for (int i = 0; i < graph.length; i++) {
if (colors[i] == 0) {
colors[i] = 1;
flag = dfs(i, colors[i]);
if (!flag)
return flag;
}
}
return flag;
}
public boolean dfs(int i, int color) {
boolean flag = true;
for (int it : map[i]) {
if (colors[it] == 0) {
colors[it] = -color;
flag = dfs(it, -color);
} else if (colors[it] == color) {
return false;
}
}
return flag;
}
}
截圖
