题解 | 第一题

#include <bits/stdc++.h>
#include <bits/types/FILE.h>
#include <variant>
using namespace std;

const int MAXN=1000000;

int father[MAXN];
int height[MAXN];
bool Visit[MAXN];

void Init(int n){
    for(int i=0;i<n;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 n,m;
    Init(MAXN);
    while(cin>>n>>m){
        Union(n, m);
        Visit[n]=true;
        Visit[m]=true;
    }
    int ans=0;
    for(int i=0;i<MAXN;i++){
        if(!Visit[i])continue;
        if(Find(i)==i)ans++;
    }
    cout<<ans<<endl;

}

并查集的数组实现，适用面更广一点，这题就是纯粹的连通集计算