题解 | #第一题#

#include <iostream>

using namespace std;

//习题11.2 第一题

const int maxn=1000010;
int father[maxn];
int height[maxn];
int visit[maxn];

//初始化
void initial(){
    for(int i=0;i<=maxn;i++){
        father[i]=-1;
        height[i]=0;
        visit[i]=0;
    }
}

//Find
int Find(int x){
    if (father[x]==-1)return x;
    return Find(father[x]);
}

//union
void Union(int x,int y){
    int fx=Find(x);
    int fy=Find(y);
    if (fx==fy)return;
    if(height[fx]>height[fy]){
        father[fy]=fx;
    }
    else if(height[fx]<height[fy]){
        father[fx]=fy;
    }
    else{
        father[fx]=fy;
        height[fy]++;
    }
}

int components(){
    //每一个节点入度<=1，（根节点数=1，连通分量数=1||空）
    int component=0;
    for(int i=0;i<maxn;i++){
        if(!visit[i])continue;
        if(father[i]==-1)component++;//连通分量数
    }
    return component;
}

int main()
{
    int n;
    int m;
    int para1,para2;
    initial();
    while(cin>>para1>>para2){
        Union(para1,para2);
        visit[para1]=1;
        visit[para2]=1;
    }
    int ans=components();
    cout<<ans<<endl;
    return 0;
}