LeetCode785. 判断二分图

1、题目链接

https://leetcode-cn.com/problems/is-graph-bipartite/

2、解题思路

这道题的意思是，给你一个无向图（二维数组），这个无向图一开始我看的有点懵，是按照他的规则来给的，比如示例1：

[[1,3], [0,2], [1,3], [0,2]]

他这个意思是第0个点连着1和3，第1个点连着0和2，第2个点连着1和3，第3个点连着0和2

然后让你判断这个无向图是否能分成一个二分图，那何为二分图呢？他也告诉你了，就是把当前的图的节点拆分开成两个子集合，并且每条边的两个节点要分别属于那两个子集合，咋一眼看起来好像就是将边的节点分开，然后最后看某个点是否不能被分开，就好比把节点分成两类，如果某个节点既被分到第一类又被分到第二类那么就会冲突，就不符合条件，代码的话还是采用深搜来写，之前好像也有一道题是这样分的：

代码

public boolean isBipartite(int[][] graph) {
    if (null == graph || graph.length < 2) {
        return false;
    }
    int[] isInGroup = new int[graph.length];
    int currentGroup = 1;
    Arrays.fill(isInGroup, currentGroup);
    for (int i = 0; i < graph.length; i++) {
        if (isInGroup[i] == 1) {
            if (!dfs(i, graph, isInGroup, currentGroup)) {
                return false;
            }
        }
    }
    return true;
}
public boolean dfs(int pos, int[][] graph, int[] isInGroup, int currentGroup) {
    if (isInGroup[pos] != 1) {
        return isInGroup[pos] == currentGroup;
    }
    isInGroup[pos] = currentGroup;
    for (int index : graph[pos]) {
        if (!dfs(index, graph, isInGroup, -1 * currentGroup)) {
            return false;
        }
    }
    return true;
}

结果

WX20190823-221318@2x.png