染色法判定二分图

题目描述
给定一个 $n$ 个点 $m$ 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。

输入格式

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

输出格式

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

数据范围

$1 \le n,m \le 105$

输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

染色法
将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图
二分图：一定不含有奇数环，可能包含长度为偶数的环， 不一定是连通图

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int h[N],e[N],ne[N],idx;
int color[N];
int n,m;
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
int 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]){
            if(!dfs(j,3 - c)) return false;
        }else if(color[j] == c) 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);
    }
    bool flag = true;
    for(int i = 1; i <= n; i ++){
        if(!color[i]){
            flag = dfs(i,1);
        }
        if(!flag) break;
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}