小狗王题解

代码：

#include<bits/stdc++.h>
#define maxn int(2e5+10)
using namespace std;
int parent[maxn];
int fa[maxn];
int ks[maxn];
int zuxian[maxn];
int n, m;
int get(int x);
void merge(int x, int y) {
	int fx = get(x);
	int fy = get(y);
	if (fx != fy) {
		if (ks[fx] > ks[fy])
			fa[fy] = fx;
		else {
			fa[fx] = fy;
			if (ks[fx] == ks[fy])
				ks[fy]++;
		}
	}
}
int get(int x) {
	if (fa[x] == x)return x;
	return get(fa[x]);
}
bool check(int a, int b) {
	if (get(a) == get(b)) {
		return 1;
	}
	return 0;
}
void init() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
}
void he_bing(int x, int y) { //合并模板函数
	if (get(x) != get(y)) {
		merge(x, y);
	}
}
int main() {
	while(cin>>n && n){
		cin >> m;
		int ans=0;
		init();
		while (m--) {
			int z, x, y;
			cin >> x >> y;
			he_bing(x,y);
		}
		for(int i=1;i<=n;i++){
			if(get(i)==i){
				ans++;
			}
		}
		cout<<ans-1<<endl;
	}
	return 0;
}
//	while(m--){
//		int z,x,y;
//		cin>>z>>x>>y;
//		if(z%2==1){
//			he_bing(x,y);
//		}else{
//			if(check(x,y)){
//				cout<<"Y";
//			}else{
//				cout<<"N";
//			}
//			cout<<endl;
//		}
//	}