原题链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1356
题目需要我们判断给定图在某一步是否会有可能出现在所有节点。首先，我们不妨假设给定图是一条单链，那么无论何时，都是“NO”的情况，因为某一时刻总是奇点或偶点（因为点是同步的，奇点相邻总是偶点，偶点相邻总是奇点）。同理，假设给定图示一个偶圈，同样得出是“NO”的情况；最终，我们得出得出只有是寄圈的情况下才满足“YES”的情况。
所以我们的任务就是判断寄圈，这里我用的是染色法，直接对图进行深搜同时标记颜色，应该是最通用的求寄圈的方法了。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <queue>
#include <cassert>
using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")
#define pii pair<int,int>
#define clr(a) memset((a),0,sizeof (a))
#define rep(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(a);i>=(int)(b);i--)
#define inf (0x3f3f3f3f)
#define eps 1e-6
#define N 100005
#define M 4000005
#define MODN 1000000007
#define RI(x) scanf("%d", &x)
#define RII(x,y) scanf("%d%d", &x, &y)
#define RIII(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define debug puts("reach here");
typedef long long LL; int n, m, s;
int a, b;
int ne;
int head[N];
int color[N]; struct node
{
int v;
int next;
}E[M]; void add_edge(int u, int v)
{
E[ne].v = v;
E[ne].next = head[u];
head[u] = ne++;
} void init()
{
memset(head, -, sizeof head);
memset(color, , sizeof color);
ne = ;
} bool dfs(int u)
{
for(int i = head[u]; i != -; i = E[i].next)
{
int v = E[i].v;
if(color[v] == )
{
color[v] = color[u] % + ;
if(dfs(v))
return true;
}
else
{
if(((color[u] + color[v]) % ) == )
return true;
}
}
return false;
} int main()
{
int t;
RI(t);
rep(cas,,t)
{
RIII(n, m, s);
init();
rep(i,,m-)
{
RII(a, b);
add_edge(a, b);
add_edge(b, a);
}
color[s] = ;
printf("Case %d: ", cas);
if(dfs(s)) puts("YES");
else puts("NO"); }
return ;
}