题解 | #第一题#

#include <iostream>
using namespace std;
const int maxn=200000;
int father[maxn];
int height[maxn];
bool visit[maxn];
int findfather(int x){
    if(x!=father[x]) father[x]=findfather(father[x]);
    return father[x];
}
void Union(int x,int y){
    x=findfather(x);
    y=findfather(y);
    if(x==y) return;
    if(height[x]<height[y]) father[x]=y;
    else if(height[x]>height[y]) father[y]=x;
    else {
        father[y]=x;
        height[x]++;
    }
}
void init(){
    for(int i=0;i<maxn;i++){
        father[i]=i;
        height[i]=0;
        visit[i]=false;
    }
}
int main(){
    int x,y;
    init();
    while(cin>>x>>y){
        Union(x, y);
        visit[x]=true;
        visit[y]=true;
    }
    int r=0;
    for(int i=0;i<maxn;i++){
        if(visit[i]&&father[i]==i) r++; 
    }
    cout<<r<<endl;

}