hdu 畅通工程

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

简单并查集，查找同集合，建连接路。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <ctype.h>
 7 #include <iomanip>
 8 #include <queue>
 9 #include <stdlib.h>
10 using namespace std;
11 
12 int f[1010];
13 int n,m;
14 
15 void init()
16 {
17     for(int i=0;i<=n;i++)
18         f[i]=i;
19 }
20 
21 int find(int x)
22 {
23     if(x==f[x])
24         return f[x];
25     f[x]=find(f[x]);
26     return f[x];
27 }
28 
29 void Union(int x,int y)
30 {
31     int a=find(x);
32     int b=find(y);
33     if(a==b)
34         return;
35     f[a]=b;
36 }
37   
38 int main()
39 {
40     int a,b,i,j;
41     while(~scanf("%d %d",&n,&m)){
42         init(n);
43         int p=0;
44         if(n==0)
45             break;
46         for(i=0;i<m;i++){
47             scanf("%d %d",&a,&b);
48             Union(a,b);
49         }
50         for(j=1;j<=n;j++){
51             if(j==f[j])
52                 p++;
53         }
54         printf("%d
",p-1);
55     }
56 }