路径压缩 两个版本 todo 没时间可以忽略
//P185王道机试指南 并查集 天勤简易版
#include <iostream>
using namespace std;
#define maxSize 1001
int v[maxSize];
int getRoot(int x){
while(v[x] != x){
x = v[x];
}
return x;
}
int main(){
int n,m;
int x,y;
while(cin>>n>>m && n){
for(int i=1;i<=n;++i){
v[i] = i;
}
while(m--){
cin>>x>>y;
x = getRoot(x);
y = getRoot(y);
if(x!=y) v[x] = y; //此处处理太粗略
}
int count = -1;//count为所有集合的个数减一，结合实际的情况的理解即可。
for(int i=1;i<=n;++i)
if(v[i] == i) ++count;
cout<<count<<endl;
}
return 0;
}
//王道版本P186
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1000;
int father[MAXN];
int height[MAXN];
void Initial(int n){
for(int i=0;i<=n;i++){
father[i] = i;
height[i] = 0;
}
}
//之前没有检查出错误 是因为牛客网的编译器不提示错误信息
//自己：使用递推版的容易理解
//int Find(int x){
// if(x!=father[x]) father[x] = Find(father[x]);
// return father[x];
//}
int Find(int x){
while(x != father[x]){
x = father[x];
}
return x;
}
void Union(int x,int y){
x = Find(x);
y = Find(y);
if(x!=y){
if(height[x] < height[y]) father[x] = y;
else if(height[y] < height[x]) father[y] = x;
else {
father[y] = x;
height[x]++;
}
}
}
int main(){
int n,m;
while(scanf("%d",&n)!=EOF){
if(n == 0) break;
scanf("%d",&m);
Initial(n);
while(m--){
int x,y;
scanf("%d",&x);
scanf("%d",&y);
Union(x,y);
}
int answer = -1;
for(int i=1;i<=n;i++){
if(Find(i) == i) answer++;
}
printf("%d\n",answer);
}
return 0;
}
