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

继续加油~