题解 | #第一题#

#include <iostream>

using namespace std;

const int MAXN = 1000001;
int father[MAXN];
int height[MAXN];
bool visit[MAXN];

void Initial (){
	for (int i = 1; i < MAXN; i++){
		father[i] = i;
		height[i] = 0;
		visit[i] = false; 
	}
}

int Find (int x){
	if (x != father[x]){
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union (int x, int y){
	x = Find(x);
	y = Find(y);
	if (x != y){
		if (height[x] > height[y]){
			father[y] = x;
		}else if (height[y] > height[x]){
			father[x] = y;
		}else{
			father[x] = y;
			height[y]++;
		}
	}
}

int main () {
	int x, y;
	Initial();
	while (scanf("%d%d", &x, &y) != EOF){
		Union(x, y);
		visit[x] = true; 
		visit[y] = true;
	}
	int ans = 0;
	for (int i = 1; i <= MAXN; i++){
		if (father[i] == i && visit[i]){
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}