itdef

地址 https://www.papamelon.com/problem/242

解答
如果圖中沒有出現奇數環，就不會出現涂色沖突.

我們使用DFS依次遍歷圖中的點將其更迭的染成1或者2類顏色，最后看所有點是否會有沖突，即可判斷是不是二分圖。

#include <iostream>
#include <vector>
#include <memory.h>


using  namespace std;

const int N = 1010;

vector<int> gra[N];
int color[N];
int n;


bool  dfs(int curr, int fill) {
	//已經涂色 有沖突
	if (color[curr] != 0 && color[curr] != fill) return false;
	//已經涂色 且無沖突
	if (color[curr] == fill) return true;

	//涂色
	color[curr] = fill;

	for (int i = 0; i < gra[curr].size(); i++) {
		int next = gra[curr][i];
		//換個顏色 涂色下一個點
		if (false == dfs(next, 3 - fill)) return false;
	}


	return true;
}

int main()
{
	scanf("%d", &n);
		memset(color, 0, sizeof color);
		for (int i = 0; i < N; i++) { gra[i].clear(); }
		
		for (int i = 0; i < n; i++) {
			int a, b; scanf("%d%d",&a,&b);
			gra[a].push_back(b);
			gra[b].push_back(a);
		}
		int flag = 1;
		
		//逐個的更換顏色  dfs 涂色每個點
		//考慮到可能不是連通，每個點都要作為dfs起點檢測
		for (int i = 0; i < n; i++) {
			if ( false == dfs(i, 1)) {
				flag = 0; break;
			}
		}

		if (flag == 1) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	


	return 0;
}

我的視頻題解空間