题解 | #第一题#

#include <iostream>
#include <map>
using namespace std;


map<int,int> father;
map<int,int> height;

// void initial(int n){
//     for(int i=1;i<=n;i++){
//         father[i]=i;
//         height[i]=0;
//     }
// }


int find(int x){
    if(father.find(x)!=father.end()){//找到x节点
        if(father[x]!=x) father[x]=find(father[x]);
    }
    else {//
        father[x]=x;
        height[x]=0;
        }
    return father[x];
}

void Union(int a,int b){
    a=find(a);
    b=find(b);
    if(a!=b){
        if(height[a]<height[b]) father[a]=b;
        else if(height[a]>height[b]) father[b]=a;
        else {
            father[a]=b;
            height[b]++;
        }
    }
}


int main() {
    int i,j;
    while(cin>>i>>j){
        Union(i,j);
    }
    int sum=0;
    for(auto it=father.begin();it!=father.end();it++){
        if(it->first==it->second) sum++;
    }
    cout<<sum;
}
// 64 位输出请用 printf("%lld")