sdut2497A simple problem

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

并查集给定一个无向图判断s点是否在所有的环中

感觉解释有点绕边输入边判断 s不加入判断也就是s的祖先一直是s 如果两个节点的祖先一样那说明形成了环若s在环中那说明节点的祖先肯定是s 否则s不在其中

s不参与连接如果一个环中一个节点不跟相邻节点连接就形不成环除非这个节点不在这个环中

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int father[10010];
 6 int find(int x)
 7 {
 8     if(x!=father[x])
 9     father[x] = find(father[x]);
10     return father[x];
11 }
12 int main()
13 {
14     int n,m,s,i,j,k,x,y;
15     while(cin>>n>>m>>s)
16     {
17         int flag = 0;
18         for(i = 1; i <= n ;i++)
19         father[i] = i;
20         for(i = 1; i <= m ; i++)
21         {
22             cin>>x>>y;
23             if(x==s||y==s)
24             continue;
25             int tx = find(x);
26             int ty = find(y);
27             if(tx==ty)
28             {
29                 if(tx!=father[s])
30                 flag = 1;
31             }
32             else
33             father[tx] = ty;
34         }
35         if(flag)
36         cout<<"NO\n";
37         else
38         cout<<"YES\n";
39     }
40     return 0;
41 }