图算法--染色法判定二图

二分图的定义是可以把一个图的点分成两个集合，使得集合内部没有边

可以证明如果一个图可以被2染色，那么它就是一个二分图

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=1e5+10,M=2*N;
 5 int h[N],e[M],ne[M],idx;
 6 int n,m;
 7 int color[N];
 8 void add(int a,int b){
 9     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
10 }
11 bool dfs(int u,int c){
12     color[u]=c;
13     for(int i=h[u];i!=-1;i=ne[i]){
14         int j=e[i];
15         if(!color[j]){
16             if(!dfs(j,3-c)){
17                 return false;
18             }
19         }else{
20             if(color[j]==c){
21                 return false;
22             }
23         }
24     }
25     return true;
26 }
27 int main(void){
28     memset(h,-1,sizeof(h));
29     cin>>n>>m;
30     for(int i=0;i<m;i++){
31         int a,b;
32         cin>>a>>b;
33         add(a,b);
34         add(b,a);
35     }
36     bool flag=true;
37     for(int i=1;i<=n;i++){
38         if(!color[i]){
39             if(!dfs(i,1)){
40                 flag=false;
41                 break;
42             }
43         }
44     }
45     if(flag==true){
46         cout<<"Yes";
47     }else{
48         cout<<"No";
49     }
50     return 0;
51 }