原题链接：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, -1, sizeof head); memset(color, 0, sizeof color); ne = 0; } bool dfs(int u) { for(int i = head[u]; i != -1; i = E[i].next) { int v = E[i].v; if(color[v] == 0) { color[v] = color[u] % 2 + 1; if(dfs(v)) return true; } else { if(((color[u] + color[v]) % 2) == 0) return true; } } return false; } int main() { int t; RI(t); rep(cas,1,t) { RIII(n, m, s); init(); rep(i,0,m-1) { RII(a, b); add_edge(a, b); add_edge(b, a); } color[s] = 1; printf("Case %d: ", cas); if(dfs(s)) puts("YES"); else puts("NO"); } return 0; }