BFS——二分图判断

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int N=1e4;
int color[N],graph[N][N];
bool bfs(int s,int n){
    queue<int> q;
    q.push(s);
    color[s]=1;
    while(!q.empty()){
        int from=q.front();//取队头颜色，父结点
        q.pop();
        for(int i=1;i<=n;i++){//按层遍历
            if(graph[from][i]&&color[i]==-1){
                q.push(i);
                color[i]=!color[from];//染与父结点不同的颜色
            }
            if(graph[from][i]&&color[from]==color[i]){//如果已经着色检查颜色是否相同
                return false;
            }
        }
    }
    return true;
}
int main(){
    int n,m,a,b,i;
    memset(color,-1,sizeof(color));
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>a>>b;
        graph[a][b]=graph[b][a]=1;
    }
    bool flag=false;
    for(i=1;i<=n;i++){
        if(color[i]==-1&&!bfs(i,n)){
            flag=true;
            break;
        }
    }
    if(flag){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
    return 0;
}