AcWing 860 染色法判定二分图 题解（染色法判定二分图）

①二分图定义：不存在奇数环的图。一张图内的所有点可以分成A，B两个非空集合，这两个集合没有交集，且在同一集合内的两个点之间都没有边相连，这张无向图就是二分图

②染色法判定二分图思路：从初始点开始，给每个点的所有邻点染不同的颜色，如果遍历到某一步发现存在两个邻点颜色相同(矛盾情况)，说明不存在二分图，反之说明存在二分图

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int h[N], e[M], ne[M], idx;//无向图，e[]和ne[]应该是头部节点的两倍
int n, m;
int color[N];//记录每个节点的颜色

void add(int a, int b){
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++ ;  
} 

bool 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;
			//给这个相邻点染上与a点相反的颜色，颜色分别用1，2表示，3-c表示取相反颜色，如果dfs返回结果为false，表示出现了矛盾情况，就返回false 
		} 
		else if(color[j] == c) return false;//如果这个相邻点已经染过色了，且颜色与a点相同，表示出现矛盾情况，返回false 
	} 
	return true;//如果一直没有出现矛盾情况，就返回true; 
}

int main()
{
	scanf("%d%d", &n, &m);//数据规模较大，用scanf读入
	
	memset(h, -1, sizeof(h));//初始化邻接表，天才的我终于记住了
	
	while(m -- ){
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
		add(b, a);//无向图，所以一条边的正反方向都要存入邻接表 
	} 
	
	bool flag = true;//设置标记 
	
	for(int i = 1; i <= n; i ++ ){//遍历每个节点 
		if(!color[i]){//如果这个点没有被染色 
			if(!dfs(i, 1)){//如果给这个点染色时出现了矛盾情况，标记并退出 
				flag = false;
				break; 
			} 
		} 
	} 
	//如果一直没有出现矛盾情况，表示这个图是二分图 
	if(flag) puts("Yes");
	else puts("No");
	
	return 0;
}