- #include<stdio.h>
- #include<math.h>
- #include<string.h>
- #include<algorithm>
- #include<iostream>
- #include<queue>
- #include<map>
- #include<vector>
- int pre[1001];
- int find(int x)
- {
- int r=x;
- while(pre[r]!=r)
- r=pre[r];
- int i=x,j;
- while(i!=r)
- {
- j=pre[i];
- pre[i]=r;
- i=j;
- }
- return r;
- }
- int main()
- {
- int n,m,i,x,y,sum;
- while(scanf("%d %d",&n,&m)!=EOF&&n)
- {
- for(i=1;i<=n;i++)
- pre[i]=i;
- sum=n-1;
- for(i=1;i<=m;i++)
- {
- scanf("%d %d",&x,&y);
- x=find(x);
- y=find(y);
- if(x!=y)
- {
- sum--;
- pre[y]=x;
- }
- }
- printf("%d\n",sum);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3163793.html