二分图判定——染色法

怎么判定一个图是否为二分图
从其中一个定点开始，将跟它邻接的点染成与其不同的颜色，最后如果邻接的点有相同颜色，则说明不是二分图，每次用bfs遍历即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1005;
int color[maxn];//记录节点颜色
int link[maxn][maxn];//记录连通
int n,m;//点数，边数
int dfs(int x,int c){//对x节点进行c染色 ，并向下搜索是否可行
color[x]=c;
for(int i=1;i<=n;i++){
if(link[x][i]){//判断是否相连
if(color[i]==c){//如果已经染色，并且颜色一样，失败，返回0
return 0;
}
if(!color[i]) {//如果没有染色
if(!dfs(i,-c)) {//向下染色，颜色与原来相反，失败返回0
return 0;
}
}
}
}
//染色成功
return 1;
}
void judge() {//判断是否为二分图
for(int i=1;i<=n;i++) {
if(!color[i]) {//如果没有染色，就进行染色
if(!dfs(i,1)) {
printf("NOn");//如果染色失败 输出no
return;
}
}
}
printf("YESn");//正常遍历结束，输出yes
}
int main() {
scanf("%d %d",&n,&m);
int x,y;
for(int i=0;i<m;i++) {
scanf("%d %d",&x,&y);
link[x][y]=1;
link[y][x]=1;
}
judge();//进行判断
}

最后

以上就是漂亮茉莉为你收集整理的二分图判定——染色法的全部内容，希望文章能够帮你解决二分图判定——染色法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。