染色法

$O(n+m)$

C++ 代码

/*
图上dfs
子集数
排列树

二分图的定义：二分图是一个无向图，其顶点可以分为两个互不相交的集合，u，v
使得图中所有的边都连接u，v，即同一个集合内没有边

存在二分图<--->图中没有奇数条边的环
染色法：
工具：color
1.遍历所有顶点去染色；（因为不能保证所有的顶点都在一个连通分支上）
2.搜索：对当前点染色，之后去搜锁那些没有染过色的点，
对于那些染过色点，如果它与即将要染的色冲突，（即不是同一个颜色）则直接返回false

*/

#include<iostream>
#define N 100010
#include<cstring>
using namespace std;

    int n,m;
int e[2*N],ne[2*N],h[N],idx;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int color[N];
bool dfs(int index,int cl){
    color[index]=cl;
    for(int i=h[index];i!=-1;i=ne[i]){
        int v=e[i];
        if(!color[v]){
            if(!dfs(v,3-cl))return false;

        }else if(color[v]!=(3-cl)){
            return false;
        }
    }
    return true;

}

int main(){
    memset(h,-1,sizeof h);

    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;

        add(a,b);
        add(b,a);

    }
    int p=true;
   for(int i=1;i<=n;++i){
       if(!color[i]){

          if(!dfs(i,1)){
           p=false;
           break;
          }
       }

   }
   if(p)cout<<"Yes"<<endl;
   else cout<<"No"<<endl;

    return 0;
}