【数据结构与算法】用染色法判定二分图

问题描述

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。

方法

在这里插入图片描述

实现

使用bfs实现

#include <iostream>
#include<cstring>
#include <algorithm>
#include<queue>

using namespace std;
const int N =100010;
int e[2*N],ne[2*N],h[N];
int color[N]; // 0无色，1色， -1色
int n,m,idx;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool pandin(){
    for(int i = 1; i<=n; i++){
        if(color[i]==0){
            color[i] = 1;
        }
        
        queue<int> q;
        q.push(i);
    while(!q.empty()){
        int u = q.front();
        //cout<<"当前判定节点："<<u<<endl;
        q.pop();
        for(int j = h[u]; j!=-1; j=ne[j]){
            int x = e[j];
            //cout<<"与其连接的点："<<x<<endl;
            if(color[x]== 0){
                color[x] = -color[u];
                q.push(x);
            }
            else if(color[x] == color[u]){
                return false;
            }
            else{
                continue;
            }
        }
    }
   
    }
    return true;
    
}


int main(){
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    int a,b;
    for(int i=1; i<=m; i++){
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    if(pandin()){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    
    
    
    
    
    
}