http://acm.hdu.edu.cn/showproblem.php?pid=1232

赤裸裸的并查集

#include<stdio.h>
int a[1010];
int findx(int x)
{
 while(a[x]!=x)         //寻找根节点
  x=a[x];
 return x;
}
void merge(int x,int y)
{
 int fx,fy;
 fx=findx(x);
 fy=findx(y);
 if(fx!=fy)
  a[fx]=fy;
}
int main()
{
 int n,m,count,i,x,y;
 while(scanf("%d",&n)!=EOF&&n)
 {
  scanf("%d",&m);
  for(i=1;i<=n;i++)
   a[i]=i;
  for(i=1;i<=m;i++)
  {
   scanf("%d%d",&x,&y);
   merge(x,y);
  }
  count=-1;
  for(i=1;i<=n;i++)
   if(a[i]==i)
    count++;
  printf("%d\n",count);
 }
 return 0;
}