题解 | #第一题#

#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;
}