畅通工程

http://acm.hdu.edu.cn/showproblem.php?pid=1232
并查集入门，模板题
 1 #include <bits/stdc++.h>
 2 #define maxn 1005
 3 typedef long long ll;
 4 using namespace std;
 5 //---------AC(^-^)AC---------\
 6 
 7 struct Node
 8 {
 9     int pre;
10     int deep;
11 }node[maxn];
12 int get_pre(int x)
13 {
14     if(node[x].pre==x)
15         return node[x].pre;
16     return node[x].pre=get_pre(node[x].pre);
17 }
18 void unite(int a,int b)
19 {
20     a=get_pre(a);
21     b=get_pre(b);
22     if(node[a].deep>node[b].deep)
23         node[b].pre=a;
24     else{
25         node[a].pre=b;
26         if(node[a].deep==node[b].deep)
27             node[b].deep++;
28     }
29 }
30 void build()
31 {
32     for(int i=1;i<=maxn;i++)
33     {
34         node[i].pre=i;
35         node[i].deep=0;
36     }
37     return ;
38 }
39 int main()
40 {
41     int n,m;
42     while(~scanf("%d",&n)&&n)
43     {
44         build();
45         scanf("%d",&m);
46         for(int i=0;i<m;i++){
47             int x,y;
48             scanf("%d%d",&x,&y);
49             unite(x,y);
50         }
51         int ans=0;
52         for(int i=1;i<=n;i++)
53         {
54             if(node[i].pre==i)
55                 ans++;
56         }
57         printf("%d
",ans-1);
58     }
59     return 0;
60 }
View Code