LeetCode 785. 判断二分图

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