思路
这里用到图论里面一个很重要的性质：
当且仅当图中不含奇数环（ 必要性），这个图才可以是二分图。
一个图是二分图（将所有的点分成两份，使得所有的边在集合之间而集合内部没有边）（通俗来说就是，任意边的两个端点不是一个集合中的）
奇数环指的是一个环中的边数为奇数，
*1找到一个未染色的点，染成黑色。
*2将这个点所有相邻的点染成白色
如果图中不含奇数环，那么染色过程不会有矛盾
for(i = 0; i < n; i ++)
if(i未染色)
dfs(i，1);染色i所在的连通块
例题
给定一个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 一定要括号括起来，不然逻辑不通。