HDU-3478 Catch(二分圖染色+并查集)

題意：

給一個無向圖和小偷所在的起點，小偷每秒可以向相連的點出發，警察想知道會不會存在一個時間點小偷出現在每個點都有可能。

思路：

畫幾個圖可以發現，圖不連通的時候，必定是NO。如果圖連通，會發現小偷的移動就是二分圖的A部和B部在交替，而如果圖不是一個二分圖，那麼小偷就能通過奇數環(二分圖的環都是偶環)，讓兩部的點混合導緻可以同時出現。即當圖不是二分圖且是連通圖時YES，否則NO。特判n==1時YES(沒啥用，資料水

)。

代碼：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> G[maxn];
int col[maxn];
int t, n, m, s;
int f[maxn];
int getF(int x){return x==f[x]? x: f[x]=getF(f[x]);}
bool dfs(int u, int fa, int key)
{
	for(int i = 0; i < G[u].size(); ++i)
	{
		int v = G[u][i];
		if(v == fa) continue;
		if(col[v] == key) return false;
		if(col[v] == (key^1)) continue;
		col[v] = key^1;
		if(!dfs(v, u, key^1)) return false;
	}
	return true;
}
int main()
{
	scanf("%d", &t);
	for(int _ = 1; _ <= t; ++_)
	{
		scanf("%d %d %d", &n, &m, &s);
		memset(col, -1, sizeof col);
		for(int i = 0; i < n; ++i)
		G[i].clear(), f[i] = i;
		for(int i = 1; i <= m; ++i)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
			f[getF(u)] = getF(v);
		}
		printf("Case %d: ", _);
		bool flag = false;
		for(int i = 1; i < n; ++i)
		if(getF(f[i]) != getF(f[0])) flag = true;
		col[s] = 0;
		if(!flag) flag = dfs(s, -1, 0);
		if(!flag || n == 1) puts("YES");
		else puts("NO");
	}
	return 0;
}
           

繼續加油~