题解 | 第一题

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