#include<stdio.h>
int father[
1005];
int find(
int x)
{
int r=
x;
while(father[r]!=
r)
{//沿着关系一直向上摸索
r=
father[r];
}
int i=
x,k;
//压缩
while(i!=
r)
{//若直接上级不是最终老大
k=
father[i];
father[i]=r;
//就直接与老大相连
i=
k;
}
return r;
}
void merge(
int x,
int y)
{
int fx,fy;
fx=find(x);
//找x的老大
fy=
find(y);
if(fx!=fy)
//是否同一个老大
{
father[fx]=fy;
//fy做fx的老大
}
}
int main()
{
int n,m,i;
while(scanf(
"%d",&n)!=
EOF,n)
{
scanf("%d",&
m);
for(i=
0;i<=n;i++
)
father[i]=
i;
while(m--
)
{
int a,b;
scanf("%d%d",&a,&
b);
if(a>
b)
merge(a,b);
else
merge(b,a);
}
int ans=
0;
for(i=
1;i<=n;i++
)
if(father[i]!=
i)
ans++
;
printf("%d\n",n-ans-
1);
}
return 0;
}
转载于:https://www.cnblogs.com/mochenmochen/p/5156848.html
