hdu1232 参考答案

   1 /*
   2 hdu1232 畅通工程,经典并查集
   3 ymc 2008/09/28
   4 题目大意:
   5 有n个诚实,某些城市有道路连接,至少要再建多少条路,使得
   6 所有道路都联通。
   7 分析与解题思路:
   8 经典并查集题目，合并m次后，统计有多少个集合。
   9 */
  10 #include <iostream>
  11 using namespace std;
  12 const int N=1010;
  13 int p[N];
  14 int n,m;
  15 void Merge(int x,int y)
  16 {
  17     int rx=x;
  18     int ry=y;
  19     while(p[rx]!=-1)//搜索x的树根
  20         rx=p[rx];
  21     while(p[ry]!=-1)//搜索y的树根
  22         ry=p[ry];
  23     int i=x;
  24     int t;
  25     while(p[i]!=-1)//压缩x
  26     {
  27         t=p[i];
  28         p[i]=rx;
  29         i=t;
  30     }
  31     i=y;
  32     while(p[i]!=-1)//压缩y
  33     {
  34         t=p[i];
  35         p[i]=rx;
  36         i=t;
  37     }
  38     if(ry!=rx)//合并
  39         p[ry]=rx;
  40     return;
  41 }
  42 int main()
  43 {
  44     int x,y;
  45     while(scanf("%d",&n)!=EOF)
  46     {
  47         if(n==0)
  48             break;
  49         scanf("%d",&m);
  50         memset(p,-1,sizeof(p));
  51         for(int i=0;i<m;i++)
  52         {
  53             scanf("%d %d",&x,&y);
  54             Merge(x,y);
  55         }
  56         int ans=0;
  57         for(int i=1;i<=n;i++)
  58             if(p[i]==-1)
  59                 ans++;
  60         printf("%d\n",ans-1);
  61     }
  62 }