hdu 2120(并查集判环）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2120

思路：简单的并查集判环应用，即如果当前的两个节点在同一个集合中，那么说明存在环了，ans++。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 1000+10
 7 int parent[MAXN];
 8 int n,m;
 9 
10 int Find(int x)
11 {
12     int s;
13     for(s=x;parent[s]>=0;s=parent[s])
14     ;
15     while(x!=s){
16         int tmp=parent[x];
17         parent[x]=s;
18         x=tmp;
19     }
20     return s;
21 }
22 
23 void Union(int u,int v)
24 {
25     int r1=Find(u),r2=Find(v);
26     if(r1==r2)return ;
27     if(parent[r1]<parent[r2]){
28         parent[r1]+=parent[r2];
29         parent[r2]=r1;
30     }else {
31         parent[r2]+=parent[r1];
32         parent[r1]=r2;
33     }
34 }
35 
36 int main()
37 {
38     int u,v,ans;
39     while(~scanf("%d%d",&n,&m)){
40         memset(parent,-1,(n+2)*sizeof(int));
41         ans=0;
42         while(m--){
43             scanf("%d%d",&u,&v);
44             if(Find(u)==Find(v)){
45                 ans++;
46             }else
47                 Union(u,v);
48         }
49         printf("%d\n",ans);
50     }
51     return 0;
52 }

View Code