sdut 2497 A simple problem （并查集 or dfs）

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2497

题意：给定一个无向图和一个点 s 求是否图中的所有环都包含点s （保证图中至少有一个环）

题解： dfs 求解只要搜到一个被访问过的点而且这个点不是 s 那么就有环不含有 s

View Code

1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define inf 99999999
12 #define maxn 15000
13 #define CL(a,b) memset(a,b,sizeof(a))
14 #define  ll  long long
15 //#define mx 1000010
16 using namespace std;
17 int n, m ,s;
18 struct node
19 {
20     int from ;
21     int to ;
22     int next ;
23 }p[maxn*20] ;
24 int head[maxn] ;
25 int cnt ;
26 void add(int u,int v)
27 {
28     p[cnt].from = u;
29     p[cnt].to = v;
30     p[cnt].next = head[u] ;
31     head[u] = cnt++ ;
32 }
33 int f ;
34 int vis[maxn] ;
35 int num ;
36 void dfs(int x,int fa)
37 {
38     vis[x] = ++num ;// 时间戳
39     if(f) return ;
40     for(int i = head[x];i!= -1 ;i = p[i].next)
41     {
42         int to = p[i].to ;
43
44        if(to == fa)continue ;
45         if(vis[to])
46         {
47             if(to != s && vis[to] < vis[x])// 一个被访问了的点  ，不是 s  而且这个点的时间戳早于本身
48             {
49
50
51                 f = 1 ;
52                 return ;
53
54             }
55             else   continue ;
56
57
58         }
59         else
60         {
61
62             dfs(to,x) ;
63         }
64
65
66
67     }
68 }
69 int main()
70 {
71     int i ,a,b;
72     while(scanf("%d%d%d",&n,&m,&s)!=EOF)
73     {
74         cnt = 0  ;
75         CL(head,-1) ;
76         for(i = 0; i < m;i++)
77         {
78             scanf("%d%d",&a,&b) ;
79             add(a,b);
80             add(b,a);
81
82         }
83
84         CL(vis,0) ;
85         f = 0 ;
86         num = 0 ;
87         dfs(s,-1) ;
88
89
90         if(f)printf("NO\n");
91         else printf("YES\n") ;
92     }
93 }

题解2：并查集：

若 s 包含在所有的环中那么去掉与 s 相关联的边之后图中一定没有环，否则， s 不包含在所有的环中。

View Code