P1536 村村通

这题基本也就是一个裸的并查集，但该题求的是不同的集合数量，倒也有一点点区别

顺带一提，题目中说的两个城市之间可能有多条路线，emmmmmm，我管你之前有没有路径，再建一次又不会吃亏。。。

 1 #include<set>
 2 #include<map>
 3 #include<list>
 4 #include<queue>
 5 #include<stack>
 6 #include<string>
 7 #include<cmath>
 8 #include<ctime>
 9 #include<vector>
10 #include<bitset>
11 #include<memory>
12 #include<utility>
13 #include<cstdio>
14 #include<sstream>
15 #include<iostream>
16 #include<cstdlib>
17 #include<cstring>
18 #include<algorithm>
19 using namespace std;
20 
21 int n,m,ans;
22 int zy[1005];
23 bool zzy[1005];//由不同的代表元可以求出不同的集合个数
24 
25 int find(int zyy){//查找该集合代表元
26     if(zyy==zy[zyy]){
27         return zyy;
28     }
29     return zy[zyy]=find(zy[zyy]);
30 }
31 
32 int main(){
33     while(1){
34         scanf("%d",&n);
35         if(n==0)return 0;//结束标志
36         scanf("%d",&m);
37         for(int i=1;i<=n;i++){
38             zy[i]=i;
39         }
40         for(int i=1;i<=m;i++){
41             int z,y;
42             scanf("%d%d",&z,&y);
43             zy[find(z)]=zy[find(y)];//合并操作
44         }
45         memset(zzy,0,sizeof(zzy));//初始化
46         ans=0;
47         for(int i=1;i<=n;i++){
48             if(!zzy[find(i)]){//若是一个新的代表元，则是一个新的集合
49                 ans++;
50                 zzy[find(i)]=true;
51             }
52             //printf("%d ",zy[i]);
53         }
54         printf("%d
",ans-1);//是输出还需要几条路径，即为不同的集合数减一
55     }
56     return 0;
57 }

emmmm也不是什么难题，没得讲了