http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1356
题意：给出一个起始点，一些边，有人从这个起始点开始随意走，问在某一个时候，它是否可以处于任意位置。
思路：思考下，就可以明白，只要是一个联通图，并且存在奇数点形成的环，那么在某一个时候就可以处于任意位置。
如何判断存在一个奇数点形成的环？
染色法：就是给每个点进行标号，标为-1，1如果存在一条边连接的两个点标号相同，那么就是存在一个奇数环......
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<math.h> #include<vector> using
namespace std; vector<int
> g[100002]; int
vis[100002],ans; void
find1(int
u,int x,int f) { if(vis[u]!=-1) { if(vis[u]!=x) ans=1; return
; } if(ans) return
; vis[u]=x; for(int
i=0;i<g[u].size();i++) { int
v; v=g[u][i]; if(v!=f) find1(v,!x,u); } } int
main() { int
t,n,m,s,i,a,b,p=1; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&s); for(i=0;i<=n;i++) g[i].clear(); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } memset(vis,-1,sizeof(vis)); ans=0; find1(s,0,-1); if(ans) printf("Case %d: YES\n",p++); else
printf("Case %d: NO\n",p++); } return
0; } |
csu1356 ：判断一个环是否为奇数环,布布扣,bubuko.com
原文：http://www.cnblogs.com/ziyi--caolu/p/3632644.html