思路：
判定二分图的算法很简单，就是用代码解决「双色问题」。
说白了就是遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色，且相邻节点的颜色都不相同。
class Solution {
boolean a=true;
boolean[] marked;
boolean[] color;
public boolean isBipartite(int[][] graph) {
int n=graph.length;
marked=new boolean[n];
color=new boolean[n]; // 自动初始化为全false;
//遍历每个顶点
for(int i=0;i<n;i++){
dfs(graph,i);
}
return a;
}
void dfs(int[][] graph,int s){
//终止条件：不是二分数则无需再递归
if(!a){
return;
}
marked[s]=true;
//遍历邻接表
for(int k:graph[s]){
if(!marked[k]){ //节点未访问过
//上色 ！
color[k]=!color[s]; // s 和k相邻! 所以上不同的色！
dfs(graph,k);
}//节点已被访问过
if(color[k]==color[s]){ // 相邻的s和v颜色相同则不是二分图
a=false;
}
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89262.html
