785. Is Graph Bipartite? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean isBipartite(int[][] graph) {
        // 状态数组，值为 0 表示未访问过，-1 与 1 对应两种颜色
        int[] states = new int[graph.length];

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < graph.length; i++) {
            if (states[i] != 0) {
                continue;
            }

            // 当前节点未访问过，染色并入队
            states[i] = 1;
            queue.offer(i);
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int neighbor : graph[node]) {
                    if (states[neighbor] == states[node]) {
                        return false;
                    }
                    if (states[neighbor] != 0) {
                        continue;
                    }
                    states[neighbor] = -states[node];
                    queue.offer(neighbor);
                }
            }
        }

        return true;
    }
}

References

785. Is Graph Bipartite?
剑指 Offer II 106. 二分图