题解 | #第一题#

- 并查集

#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]=1;
        visit[i]=false;
    }
    return ;
}
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)return;
    if(height[x]>height[y]){
        Father[y]=x;
    }
    else if(height[x]<height[y]){
        Father[x]=y;
    }
    else {
        Father[x]=y;
        height[y]++;
    }
    return;
}

int countnum(){
    int sum=0;//连通分量
    for(int i=0;i<maxn;i++){
        if(!visit[i])continue;
        if(Find(i)==i)sum++;
    }
    return sum;
}

 int main(){
     int  n,m;
     Initial();
     while(scanf("%d %d",&n,&m)!=EOF){
             Union(n,m);
             visit[n]=true;
             visit[m]=true;
     }
     cout<<countnum()<<endl;
     return 0;
 }

也可用map的映射关系取代数组（但开销更大）

#include<iostream>
#include<map>
using namespace std;

map<int,int>Father;
map<int,int>height;

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)return;
    if(height[x]>height[y]){
        Father[y]=x;
    }
    else if(height[x]<height[y]){
        Father[x]=y;
    }
    else {
        Father[x]=y;
        height[y]++;
    }
    return;
}

int countnum(){
    int sum=0;//连通分量
    map<int,int>::iterator it;
    for(it=Father.begin();it!=Father.end();it++){
        if(it->first==it->second)sum++;
    }
    return sum;
}

 int main(){
     int  n,m;

     while(scanf("%d %d",&n,&m)!=EOF){
         if(Father.find(m)==Father.end()){//第一次要建立映射关系
             Father[m]=m;
             height[m]=1;
         }
         if(Father.find(n)==Father.end()){//
             Father[n]=n;
             height[n]=1;
         }
             Union(n,m);
     }
     cout<<countnum()<<endl;
     return 0;
 }