力扣 785 判断二分图

题意：给定一堆graphes，判定他们是否是二分图

思路：遍历每一个二分图的节点，遍历的时候，检查相邻的两个节点不能有相同的颜色，这里用1和－1标示，具体见代码

思想：染色法

复杂度：时间O（n²)，空间O(n)

class Solution {
    // key是节点的index，value是节点染色的值
    HashMap<Integer, Integer> map = new HashMap();
    public boolean isBipartite(int[][] graph) {
        // graph会有多个独立的闭环
        for(int i=0;i<graph.length;i++) {
            // 没遍历过当前节点，且当前节点不是Bipartitle
            if(!map.containsKey(i) && !isBi(i, graph))
                return false;
        }
        return true;
    }
    
    // 检查以当前节点开始的graph是否事Bipartitle
    boolean isBi(int index, int[][] graph) {
        Queue<Integer> queue = new LinkedList();
        // 把首节点加入队列
        queue.add(index);
        // 遍历过的节点加入map
        map.put(index, 1);
        while(!queue.isEmpty()) {
            // 从对列中弹出节点
            int cur = queue.poll();
            int sign = map.get(cur);
            // 查看当前节点的邻居节点
            for(int i: graph[cur]) {
                // 邻居节点之前出现过
                if(map.containsKey(i)) {
                    int tsign = map.get(i);
                    // 邻居节点和当前节点染色相同
                    if(tsign == sign)
                        return false;
                } else {
                    // 邻居节点加入队列，并加入map
                    queue.add(i);
                    map.put(i, sign*(-1));
                }
            }
        }
        return true;
    }
}