题解 | #第一题#
第一题
https://www.nowcoder.com/practice/7c29cdfa28274c86afc9e88c07448a10
经典的并查集的题目，但要注意数量级。
这里用map解决了。
#include<cstdio>
#include<unordered_map>
using namespace std;
typedef long long LL;
// first是 father
// second 是 height
unordered_map<LL, pair<LL, LL>> myMap;
LL find(LL x){
if(x != myMap[x].first)
x = find(myMap[x].first);
return x;
}
void Union(LL x, LL y){
x = find(x);
y = find(y);
if(x != y) {
if(myMap[x].second > myMap[y].second)
myMap[y].first = x;
else if(myMap[x].second < myMap[y].second)
myMap[x].first = y;
else {
myMap[y].first = x;
++myMap[x].second;
}
}
}
int main(){
LL a,b;
while(scanf("%lld %lld", &a, &b)!=EOF){
if(myMap[a].first == 0)
myMap[a] = make_pair(a, 0);
if(myMap[b].first == 0)
myMap[b] = make_pair(b, 0);
Union(a, b);
}
LL number = 0;
unordered_map<LL, pair<LL, LL>>::iterator i = myMap.begin();
for(;i!=myMap.end();++i)
if(find(i->first) == i->first)
++number;
printf("%lld", number);
return 0;
}
