题解 | #第一题#

//就是最原始的并查集
#include <iostream>
using namespace std;

int father[1000000];
int height[1000000];
int visit[1000000];
void Initial()
{
    for(int i=0;i<1000000;i++)
    {
        father[i]=i;
        height[i]=0;
        visit[i]=0;
    }
}

int Find(int x)
{
    if(father[x]==x)return x;
    else 
    return Find(father[x]);
}

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

int main() {
    int a, b;
    Initial();
    while (cin >> a >> b) { 
        Union(a,b);
        visit[a]=1;
        visit[b]=1;
    }
    int root=0;
    for(int i=0;i<1000000;i++)
    {
        if(visit[i]){
            if(i==Find(i))root++;
        }
    }
    cout<<root<<endl;
}