染色法
思路
这里用到图论里面一个很重要的性质：
当且仅当图中不含奇数环（ 必要性），这个图才可以是二分图。
一个图是二分图（将所有的点分成两份，使得所有的边在集合之间而集合内部没有边）（通俗来说就是，任意边的两个端点不是一个集合中的）奇数环指的是一个环中的边数为奇数，*1找到一个未染色的点，染成黑色。
*2将这个点所有相邻的点染成白色如果图中不含奇数环，那么染色过程不会有矛盾
for(i = 0; i < n; i ++) if(i未染色)dfs(i，1);染色i所在的连通块
例题：AcWing 860. 染色法判定二分图
给定一个n个点m条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。
输出格式
如果给定图是二分图，则输出“Yes”，否则输出“No”。
数据范围
1≤n,m≤105
输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;/* *5 */int n, m;
int ne[M], e[M], h[M], idx = 0;
int cl[N];void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool dfs(int u, int c){cl[u] = c;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(!cl[j]){if(!dfs(j, 3 - c)) return false; /* *20 */}/* 21 */else if(cl[j] == c) return false; }return true;
}
int main(){cin >> n >> m; memset(h, -1, sizeof h);while(m --){int a, b ;cin >> a >> b;add(a, b);add(b, a);}bool flag = 1;for(int i = 1; i <= n; i ++)if(!cl[i])if(!dfs(i, 1)){flag = 0;break;}if(flag) cout << "Yes";else cout << "No";return 0;}
*5 无向图
*20 这里cl值有0, 1, 2三个，0代表未上色，1代表红色，2代表蓝色。
*21 一定要括号括起来，不然逻辑不通。