最简单的并查集
hdu1232

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1050;
int p[N];
int n,m;
void init(){
   
    for(int i=1;i<=n;i++){
   
        p[i]=i;
    }
}
int find(int x){
   
    return p[x]==x ? x : p[x]=find(p[x]);
}
void unit(int a,int b){
   
    p[find(a)]=find(b);
}
bool isUnit(int a,int b){
   
    return find(a)==find(b);
}
int main(void){
   
    while(~scanf("%d",&n) && n){
   
        scanf("%d",&m);
        init();
        int u,v;
		//n个节点如果都不连通,需要加n-1条边
        int res=n-1;
        for(int i=0;i<m;i++){
   
            scanf("%d%d",&u,&v);
			//如果有两个节点连通的话,需要的边就少了一条
            if(!isUnit(u,v)){
   
                res--;
				//再把这两个点连通
                unit(u,v);
            }
        }
        printf("%d\n",res);
    }
    return 0;
}