The coloring method determines the bipartite graph acwing 860 Chromatic judgement bipartite graph

Determine bipartite graph by coloring AcWing 860. Determine bipartite graph by coloring

Original link

AcWing 860. Determine bipartite graph by coloring

Algorithm tags

Bipartite graph decision Dyeing method

Ideas

A bipartite graph can divide all points into sets on both sides , Make all edges outside and between two sets , There are no edges inside the set
Necessary and sufficient conditions for bipartite graph

adequacy
It can be constructed by , Dye the color of a point in the figure into color 1, Then the adjacent dots are dyed as color 2

prove ：
Reduction to absurdity , If there is an odd ring , There must be contradictions

Cause , Dye every point in the graph , Judge whether there are contradictions .
If there are contradictions, it is not a bipartite graph , Otherwise, it indicates that it can be dyed , It's a bipartite graph .

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005, INF = 0x3f3f3f3f;
//  Store undirected graph   You need to store both sides at the same time   Therefore, you need to set the array e[], ne[] Open up twice the space 
int e[N*2], ne[N*2], h[N], idx;
int color[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void add(int a, int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool dfs(int u, int c){
    color[u]=c;
    for(int i=h[u]; i!=-1; i=ne[i]){
        int j=e[i];
        if(!color[j]){
        	//  Adjacent nodes dfs Same color after 
            if(!dfs(j, 3-c)){
                return false;
            }
        }else if(color[j]==c){//  Adjacent nodes have the same color 
            return false;
        }
    }
    return true;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=read(), m=read();
    memset(h, -1, sizeof h);
    while(m--){
        int a=read(), b=read();
        add(a, b), add(b, a);
    }
    bool flag=true;
    rep(i, 1, n+1){
        if(!color[i]){
            if(!dfs(i, 1)){
                flag=false;
                break;
            }
        }
    }
    if(flag){
        puts("Yes");
    }else{
        puts("No");
    }
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support