洛谷 P1536 村村通（并查集）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int f[100005];
 8 int n, m, x, y;
 9 
10 inline int find(int x){
11     if(x != f[x])
12         f[x] = find(f[x]);
13     return f[x];
14 }//"查 "
15 
16 int main(){
17     while(true){
18         int ans = 0;
19         scanf("%d", &n);
20         if(n == 0)
21             return 0;//结束 
22         scanf("%d", &m);
23         for(int i = 1; i <= n; i++)
24             f[i] = i;
25         for(int i = 1; i <= m; i++){
26             scanf("%d%d", &x, &y);
27             int r1 = find(x);
28             int r2 = find(y);
29             if(r1 != r2){
30                 f[r1] = r2;
31             }//"并"  
32         }
33         for(int i = 1; i <= n; i++){
34             if(find(i) == i){//没与任何点并在一起 
35                 ans++;//点的个数 
36             }
37         }
38         printf("%d\n", ans - 1);//要修的路的条数 
39     }
40     return 0;
41 }