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;
}
继续加油~