A simple problem(并查集判环)

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

题意：给定一些点和边的关系，判断S点是否在所构成无向图的所有环里。

思路：用并查集将所有（除去S及与 S有关的点）有关系的点放在一个集合里，若此时图中还存在环，那么一定不包含S。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int maxn = 10002;
 4 
 5 int f[maxn],n;
 6 int find(int x)
 7 {
 8     if (x!=f[x])
 9         f[x] = find(f[x]);
10     return f[x];
11 }
12 void merge(int x,int y)
13 {
14     x = find(x);
15     y = find(y);
16     if (x!=y)
17         f[x] = y;
18 }
19 void init()
20 {
21     for (int i = 0; i <= n; i ++)
22         f[i] = i;
23 }
24 int main()
25 {
26     int m,s;
27     while(~scanf("%d%d%d",&n,&m,&s))
28     {
29         init();
30         int u,v,flag = 1;
31         for (int i = 0; i < m; i ++)
32         {
33             scanf("%d%d",&u,&v);
34             if (u!=s && v!=s)
35             {
36                 if (find(u)==find(v))//判断环
37                     flag = 0;
38                 merge(u,v);//合并集合
39             }
40         }
41         if (flag)
42             printf("YES
");
43         else
44             printf("NO
");
45     }
46     return 0;
47 
48 }

View Code