染色法判定二分图

算法1:时间复杂度 O(m)

C++ 代码

#include<iostream>
using namespace std;
const int N =1e5 + 10;
int s[N],n,m;

int main(){
    cin>>n>>m;
    bool flag=true;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(!s[a] && !s[b]){
            s[a]=1;
            s[b]=2;
        }else if(s[a]&&!s[b]){
            s[b]=3-s[a];
        }else if(s[b]&&!s[a]){
            s[a]=3-s[b];
        }else{
            if(s[a]+s[b]!=3) {
               flag=false;   
            }
        }
    }
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

算法2:时间复杂度 O(n+m)

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
// 原理：当且仅当图中不含奇数环（通过染色，不可能一个顶点两个颜色）

// N 表示顶点数的极值
// M 表示边数的极值
const int N = 100010,M = 200010;
// 采用邻接表存储(通过有向图，无向图看作一种特殊的有相图)
// h[N] 表示邻接表的头节点
// e[M] 表示链表节点的值
// ne[M] 表示链表指向下一节点的指针
// idx 表示第几个插入的节点，便于操作链表
// color[N] 表示该节点的颜色
int h[N],e[M],ne[M],idx,color[N];
// n个点 m条边
int n,m;
// 邻接表添加节点
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
// 深度优先搜索
bool dfs(int u,int c){
    // 给节点u染色
    color[u]=c;
    // 遍历u连通的节点
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        // 如果j没染过色,对j子树染色
        if(!color[j]){
            // 对节点j染不同的颜色，如果j子树染色失败，返回false
            if(!dfs(j,3-c)) return false;
        }
        // 如果节点j已染色，并且和u节点色彩一样，表示不是二分图，直接返回false;
        else if(color[j] == c) 
            return false;
    }
    return true;
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    int a,b;
    // 无向边通过两条有向边表示
    while(m--){
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    bool flag = true;
    // 依次对每个顶点染色
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1)){
                flag = false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}