1、题目
785. 判断二分图
2、题解
这道题目乍看之下并不难，不过写起来还是有点蛋疼。
首先，二分图是指你把点分成两个集合A、B；只有A连B的线，没有A连A，B连B。也就是说相邻节点必须是不同的两个集合。在这个题目中，几个点就是几个第二级的数组，那么通过染色区别的方法，只要相邻的节点颜色相同即为false,否则就是true.
3、代码
class Solution {
public boolean isBipartite(int[][] graph) {
int len = graph.length;
int color[] = new int[len];
//外面遍历上色，再内部循环上色，再跳到别的数组上色。
for(int i = 0;i<len;i++){
if(color[i]==0&&dfs(i,color,2,graph)==false){
return false;
}
}
return true;
}
//这种写法的节点必须是按顺序命名的，即节点必须从0加1递增，不然就不能使用这个方法。
//例：[[1,3],[0,2],[1,3],[0,2]] TRUE
//[[1,5],[0,2],[1,5],[0,2]] 数组下标越界
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、执行结果
image.png
