学步园

思路：并查集，最后结果就是块数-1

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-10
#define PI acos(-1.0)//3.14159265

const int MAX_ = 1010;
const int N = 100010;
const int INF = 0x7fffffff;

int fa[MAX_], rank[MAX_];
bool vis[MAX_];

int main(){
    int  n, m, ans, s, t;

	while(scanf("%d",&n)&&n){
	    scanf("%d",&m);

	    for(int i = 0; i <= n; ++i){
            //rank[i] = 1;
            fa[i] = i;
	    }
	    while(m--){
            scanf("%d%d",&s,&t);
            int a ,b;
            a = findfa(s);
            b = findfa(t);
            fa[a] = b;
	    }

	    mst(vis,0);
	    ans = 0;
	    for(int i = 1; i <= n; ++i){
	        int tmp = findfa(i);
            if(!vis[tmp]){
                vis[tmp] = 1;
                ans++;
            }
	    }


        printf("%d\n",ans-1);
	}
	return 0;
}