$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

一个图是二分图当且仅当这个图中不含奇数环。

染色过程：一个点的相邻点和它分属于不同的两个集合，因此可以给每个点染黑白两色，如果一个点的相邻点已经被染色并且与当前点颜色相同那么这张图不是二分图。可以用 DFS 模拟染色过程。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2;
int n, m;
int e[M], ne[M], h[N], idx, c[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int x, int color) {
    c[x] = color;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!c[j]) {
            if (!dfs(j, 3 - color)) return 0;
        }
        else if (c[j] != 3 - color) return 0;
    }
    return 1;
}
int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m--) {
        int u, v; cin>>u>>v;
        add(u, v); add(v, u);
    }
    bool ans = 1;
    for (int i = 1; i <= n; i++) {
        if (!c[i]) {
            if (!dfs(i, 1)) {
                ans = 0; break;
            }
        }
    }
    if (ans) puts("Yes");
    else puts("No");
}