题解 | 第一题

#include<iostream>

using namespace std;
const int maxn = 1000005;
int f[maxn];
int h[maxn];
bool p[maxn];
void init(){
	for(int i=0;i<maxn;i++){
		f[i] = i;
		h[i] = 0;
		p[i] = false;
	}
}
int find(int x){
	if(x!=f[x]){
		f[x] = find(f[x]);
	}
	return f[x];
}
void uniond(int x,int y){
	if(h[x]>h[y]){
		f[y] = x;
	}else if(h[y]>h[x]){
		f[x] = y;
	}else{
		f[y] = x;
		h[x]++;
	}
}
int main(){
	int n,m;
	init();
	while(cin>>n>>m){
		int c = find(n);
		int d = find(m);
		if(c!=d)uniond(c,d);
		p[n] = true;
		p[m] = true;
	}
	int num = 0;
	for(int i=0;i<maxn;i++){
		if(!p[i])continue;
		if(f[i]==i)num++;
	}
	cout<<num<<endl;
}