二分图

• OI Wiki: https://oi-wiki.org/graph/bi-graph/

题目	难度
785. 判断二分图	中等	模板题
886. 可能的二分法	中等	二部图判定

判定

二部图判定，常用方法是节点染色，即先选取图中任意一点，染成红色，再将其相邻节点染成蓝色，判定染色后是否会有相邻两个节点颜色相同，若存在相邻两个节点颜色相同，不是二部图，否则，是二部图。

785. 判断二分图

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution785 {
    public boolean isBipartite(int[][] graph) {
        int size = graph.length;

        int[] colors = new int[size];
        // -1:未染色 0:红色 1:蓝色
        Arrays.fill(colors, -1);

        for (int i = 0; i < size; i++) {
            if (colors[i] == -1) {
                if (!setColor(graph, colors, i)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean setColor(int[][] graph, int[] colors, int i) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        colors[i] = 0;

        while (!queue.isEmpty()) {
            int cur = queue.remove();

            for (int next : graph[cur]) {
                if (colors[next] != -1) {
                    if (colors[next] == colors[cur]) {
                        return false;
                    }
                } else {
                    colors[next] = 1 ^ colors[cur];
                    queue.add(next);
                }
            }
        }
        return true;
    }
}

（全文完）