 /**//*
题意:给出一个无向图,一个起点,问是否在某个时候,这个人有可能在所有点都可以出现
人不能停留在原地
画一下图就知道,只要存在奇圈,那么奇圈的点就可以任何时刻都出现人
同时,对于奇圈外的,奇圈可以源源不断地传到奇圈外
这样肯定存在某个时刻,其他点也可以同时出现人(因为源源不断传出来,所以肯定会波及所有)
*/
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

const int MAXN = 100005;

vector<int>G[MAXN];
bool flag;
int vi[MAXN];

void dfs(int u,int p,int dep)
  {
if(flag)return;
vi[u]=dep;
for(int i=0,size=G[u].size();i<size;i++)
 {
int v=G[u][i];
if(v==p)continue;
 if(vi[v]==dep) {flag=true;return;}
if(vi[v]==0)dfs(v,u,-dep);//注意是没visit过的才继续dfs
}
}
int main()
  {
int T,t=1;
scanf("%d",&T);
while(T--)
 {
printf("Case %d: ",t++);
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<n;i++)
G[i].clear();
for(int i=0,a,b;i<m;i++)
 {
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
memset(vi,0,sizeof(vi));
flag = false;
dfs(s,s,1);
puts(flag?"YES":"NO");
}
return 0;
}

|