二分图判定——染色法
【二分图判定——染色法】怎么判定一个图是否为二分图
从其中一个定点开始，将跟它邻接的点染成与其不同的颜色，最后如果邻接的点有相同颜色，则说明不是二分图，每次用bfs遍历即可。
#include
#include
#include
#include
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("NO\n");
//如果染色失败 输出no
return;
}
}
}
printf("YES\n");
//正常遍历结束，输出yes
}int main() {
scanf("%d %d",&n,&m);
int x,y;
for(int i=0;
i 
