题解 | 第一题

#include <iostream>
#include<bits/stdc++.h>

using namespace std;
//秩优化的map并查集
map<int,int>father;
map<int,int>height;
int find(int x){
    if(father.find(x)!=father.end()){
        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){
    int a1=find(a),b1=find(b);
    if(a!=b){
        if(height[a1]>height[b1]){
            father[b1]=a1;
        }
        else if(height[b1]>height[a1]){
            father[a1]=b1;
        }
        else{
            father[a1]=b1;
            height[b1]++;
        }
    }
}
int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        Union(a,b);

    }
    int sum=0;
    for(auto it=father.begin();it!=father.end();it++){
        if(it->first==it->second){
            sum++;
        }
    }
    cout<<sum<<endl;

}
// 64 位输出请用 printf("%lld")