B

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

分析:本题的实质是一个并查集问题，哎，对并查集还不是很懂,开始一直不知道用什么方法去做。并查集一般用与解决动态连通性的问题。本题关键是求出孤立的点的个数，要建的道路数为孤立点的个数-1。还有就是根据输出的结果，要注意一下怎样输入。

并查集的3种主要操作：获取根、合并两个结点所在集合、查询两个节点是否在同一集合

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int father[1007];
 5 void init()
 6 {    
 7 int i;
 8     for(i=1;i<1007;i++)
 9         father[i]=i;
10 }
11 int f(int n)
12 {
13     if(n!=father[n])
14         father[n]=f(father[n]);
15     return father[n];
16 }//获取根节点
17 void merge(int x,int y)
18 {
19  int fx,fy;
20   fx=f(x);
21   fy=f(y);
22   if(fx!=fy)
23       father[fx]=fy;
24 }
25 int main()
26 {
27   int n,m,a,b;
28   while(~scanf("%d",&n),n)
29   {
30       scanf("%d",&m);
31       init();//不要忘记初始化
32     for(int i=1;i<=m;i++)
33     {
34       scanf("%d %d",&a,&b);
35        merge(a,b);
36     }
37    int cns=0;
38     for(int j=1;j<=n;j++)
39     {      
40       if(father[j]==j)//求出孤立的点的个数
41           cns++;
42     }
43       printf("%d
",cns-1);
44   }
45 
46 return 0;
47 }

View Code