1、題目
785. 判斷二分圖
2舶沛、題解
這道題目乍看之下并不難嘹承，不過(guò)寫(xiě)起來(lái)還是有點(diǎn)蛋疼。
首先如庭，二分圖是指你把點(diǎn)分成兩個(gè)集合A叹卷、B；只有A連B的線坪它，沒(méi)有A連A骤竹，B連B。也就是說(shuō)相鄰節(jié)點(diǎn)必須是不同的兩個(gè)集合往毡。在這個(gè)題目中蒙揣，幾個(gè)點(diǎn)就是幾個(gè)第二級(jí)的數(shù)組，那么通過(guò)染色區(qū)別的方法开瞭，只要相鄰的節(jié)點(diǎn)顏色相同即為false,否則就是true.
3懒震、代碼
class Solution {
public boolean isBipartite(int[][] graph) {
int len = graph.length;
int color[] = new int[len];
//外面遍歷上色，再內(nèi)部循環(huán)上色嗤详，再跳到別的數(shù)組上色个扰。
for(int i = 0;i<len;i++){
if(color[i]==0&&dfs(i,color,2,graph)==false){
return false;
}
}
return true;
}
//這種寫(xiě)法的節(jié)點(diǎn)必須是按順序命名的，即節(jié)點(diǎn)必須從0加1遞增葱色，不然就不能使用這個(gè)方法递宅。
//例：[[1,3],[0,2],[1,3],[0,2]] TRUE
//[[1,5],[0,2],[1,5],[0,2]] 數(shù)組下標(biāo)越界
public boolean dfs(int i,int []color,int t,int [][]graph){
if(color[i]!=0){
return color[i]==t;
}
color[i] = t;
for(int j:graph[i]){
if(dfs(j,color,3-t,graph)==false){
return false;
}
}
return true;
}
}
4、執(zhí)行結(jié)果
image.png
