785. 判断二分图（图）

二分图，着色法

题目中说给出的是邻接表，可实际传参时传入的时一个矩阵，所以我用的仍然是邻接矩阵的深度优先搜索；

有关邻接表的DFS参考如下链接：
基于邻接表的图的深度优先搜索

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];//color即作为visited数组，又作为标识结点颜色的数组,-1表示未着色，0表示着蓝色，1表示着红色；
        Arrays.fill(color,-1);
        for(int start = 0;start<n;start++){
        	//需考虑图可能是非连通图，对每个连通分量都要处理
            if(color[start]==-1){
                Stack<Integer> stack = new Stack<>();
                color[start] = 0;
                stack.push(start);
                while(!stack.empty()){
                    int cur = stack.pop();
                    for(int i:graph[cur]){
                    	//如果相邻结点未访问（未着色）过
                        if(color[i] == -1){
                            stack.push(i);
                            color[i] = color[cur] ^ 1;//异或运算 0^1 = 1;1^1 = 0,实现0，1互换位置
                        }
                        else if(color[i] == color[cur])
                            return false;
                    }
                }
            }
        }

        return true;
    }
}