染色法判定二分图

什么是二分图
ans：图中所有点能被分成两个集合A，B，每个集合中所有点之间没有边相连通，集合之间的点可以存在边相连通。
由此可证该图中没有奇数环。
证明：
充分性：已只一个二分图，两个集合之间存在若干条边，但是集合内部不存在边。则如果存在环，则环的环的所有边都在两集合之间，且所有的边必须是成对存在的。
必要性：已知一个图中没有奇数环，若存在环，则为偶数环，则对于这个偶数环中任意一点，与他相邻的其他点都可以被放入对面集合中，使得所有的点在两个集合中，且集合内部都不存在边。若不存在环，则同理可证。

染色法的正确性
ans：染色法可以判断图中是否存在奇数环，若存在则染色冲突，否则不存在奇数环，则该图为二分图。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010;
int n, m;
int color[N];
int h[N], e[M], ne[M], cnt;

void add(int u, int v) {
    e[cnt] = v, ne[cnt] = h[u], h[u] = cnt++;
}

int dfs(int x, int col) {  // 从x点开始颜色，x点为col颜色
    color[x] = col;
    for (int i = h[x]; ~i; i = ne[i]) {
        if (!color[e[i]]) {
            if (!dfs(e[i], 3 - col)) return false;  // 1和2两种颜色
        } else {
            if (color[e[i]] == col) return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(v, u), add(u, v);
    }
    bool flag = true;
    for (int i = 1; i <= n; i++) {  /遍历所有点，没有染过染色，就染成1
        if (color[i]) continue;
        if (!dfs(i, 1)) {
            flag = false;
            break;
        }
    }
    if (flag) puts("Yes");
    else puts("No");

    return 0;
}