G - Ice_cream's world I （并查集）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=1010;
 8 
 9 int n,m;
10 int father[maxn];
11 
12 void makeSet(){
13     for(int i=0;i<n;i++){
14         father[i]=i;
15     }
16 }
17 
18 int findSet(int x){
19     if(x!=father[x]){
20         father[x]=findSet(father[x]);
21     }
22     return father[x];
23 }
24 
25 int main(){
26 
27     //freopen("input.txt","r",stdin);
28 
29     while(~scanf("%d%d",&n,&m)){
30         makeSet();
31         int ans=0;
32         int a,b;
33         while(m--){
34             scanf("%d%d",&a,&b);
35             int fx=findSet(a);
36             int fy=findSet(b);
37             if(fx==fy)
38                 ans++;
39             else
40                 father[fx]=fy;
41         }
42         printf("%d\n",ans);
43     }
44     return 0;
45 }