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;
}