题解 | 第一题

#include <stdio.h>
#include <vector>
using namespace std;
int father[1000000];
void InitT(){
    for(int i=0;i<1000000;++i){
        father[i]=i;
    }
}
int FindT(int u){
    if(u==father[u]){return u;}
    else{
        father[u]=FindT(father[u]);
        return father[u];
    }
}
void UnionT(int u,int v){
    int uroot=FindT(u);
    int vroot=FindT(v);
    father[vroot]=uroot;
}
int main(){
    InitT();
    vector<int> dis;
    int i,j;
while(scanf("%d%d",&i,&j)!=EOF){
    dis.push_back(i);
    dis.push_back(j);
    UnionT(i,j);
}
int root=0;
int rootcishu[1000000]={0};
for(int i=0;i<dis.size();++i){
    if(rootcishu[dis[i]]==0){
        if(father[dis[i]]==dis[i]){++root;++rootcishu[dis[i]];}
    }
}
printf("%d",root);
return 0;

}