LeetCode 785. Is Graph Bipartite?

Problem

LeetCode 785. Is Graph Bipartite?

1. 题目简述

给出一个图，判断这个图是否为二分图。

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

2. 算法思路

基础的染色二分图问题，但是要注意，对于整张图而言，它可能不是连通图，而是分为多个子图的，所以不能只遍历一种。

DFS

BFS

3. 解法

DFS：

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        // -1是未染色，0是红色，1是黑色
        Arrays.fill(color, -1);

        for (int i = 0; i < graph.length; i++) {
            if (color[i] == -1) {
                color[i] = 0;
                if (!dfs(graph, i, color)) {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean dfs(int[][] graph, int index, int[] color) {
        for (int i = 0; i < graph[index].length; i++) {
            if (color[graph[index][i]] == -1) {
                color[graph[index][i]] = color[index] ^ 1;
            } else if (color[graph[index][i]] != color[index] ^ 1) {
                return false;
            }
        }

        return true;
    }
}

BFS：

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[graph.length];
        Arrays.fill(color, -1);

        for (int i = 0; i < n; i++) {
            // 这里for循环是因为这里也可能是非连通图，再判断是否遍历过，如果遍历过则跳过；
            // 没有则说明到了新的一个连通图
            if (color[i] == -1) {
                Queue<Integer> queue = new LinkedList();
                queue.offer(i);
                color[i] = 0;

                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    for (int j = 0; j < graph[node].length; j++) {
                        if (color[graph[node][j]] == -1) {
                            color[graph[node][j]] = color[node] ^ 1;
                            queue.offer(graph[node][j]);
                        } else if (color[graph[node][j]] == color[node]) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
}