题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3478
题意：有n个路口，m条街，一小偷某一时刻从路口 s 开始逃跑，下一时刻都跑沿着街跑到另一路口，问是否存在某一时刻出，小偷可能出现在任意路口；
如果小偷能走一个环，如果这个环是偶数个节点，那么某个节点只能在偶数时刻或者奇数时刻到达；
但是如果这个环是奇数个节点，他既可以在奇数时刻到达又可以在偶数时刻到达；所以这道题就是求是否存在一个奇环；如果存在输出YES，否则NO；
由于二分图中不能含有奇环，所以我们只需用染色法判断是否是二分图即可；
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <math.h> using namespace std; #define met(a, b) memset(a, b, sizeof(a))
#define N 100003
#define INF 0x3f3f3f3f
const int MOD = 1e9+; typedef long long LL; vector<vector<int> >G; int c[N], n, m, s; int flag; void dfs(int u)
{
int len = G[u].size();
for(int i=; i<len; i++)
{
int v = G[u][i];
if(c[v] == -)
{
c[v] = c[u]^;
dfs(v);
}
else if(c[v] == c[u])
{
flag = ;
return;
}
}
return ;
} int main()
{
int T, t = ;
scanf("%d", &T);
while(T--)
{
scanf("%d %d %d", &n, &m, &s);
G.clear();
G.resize(n+);
for(int i=; i<=m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
met(c, -);
flag = ;
printf("Case %d: ", t++);
dfs(s);
if(flag)puts("YES");
else puts("NO");
}
return ;
}
dfs
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <math.h> using namespace std; #define met(a, b) memset(a, b, sizeof(a))
#define N 100003
#define INF 0x3f3f3f3f
const int MOD = 1e9+; typedef long long LL; vector<vector<int> >G; int c[N], n, m, s; int bfs()
{
met(c, -);
queue<int>Q;
Q.push(s);
c[s] = ;
while(!Q.empty())
{
int p = Q.front();Q.pop();
int len = G[p].size(), q;
for(int i=; i<len; i++)
{
q = G[p][i];
if(c[q] == -)
{
c[q] = c[p]^;
Q.push(q);
}
else if(c[q] == c[p])
return ;///说明存在奇环，不是二分图；
}
}
return ;
} int main()
{
int T, t = ;
scanf("%d", &T);
while(T--)
{
scanf("%d %d %d", &n, &m, &s);
G.clear();
G.resize(n+);
for(int i=; i<=m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
printf("Case %d: ", t++);
if(bfs())puts("YES");
else puts("NO");
}
return ;
}
bfs