题解 | #第一题#

耍赖皮，用散列表

#include <cstdio>
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

unordered_map<int, int> parent;
vector<int> v;

int Find(int x){
	if(!parent.count(x)){
		return x;
	}
	return Find(parent[x]);
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		parent[y] = x;//暴力一点,省事 
	}
}

int main(){
	int x, y;
	while(scanf("%d%d", &x, &y) != EOF){
		v.push_back(x);
		Union(x, y);
	}
	int cnt = 0;
	sort(v.begin(), v.end());
	for(int i=0; i<v.size(); i++){
		if(i && v[i] == v[i-1]){
			continue;
		}
		if(!parent.count(v[i])){
			cnt++;
		}
	}
	printf("%d\n",cnt);
	return 0;
}