加边的无向图--并查集

加边的无向图

知识点：并查集

题意：题意简单，给你n个点，m条边，要你求至少要在这个的基础上加多少条无向边使得任意两个点可达。

题解：并查集裸题，直接套用模板即可。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll father[1000010];
void init(){//初始化
    for(ll i=1;i<=1000010;i++){
        father[i]=i;
    }
}
ll find (int x){//寻找父节点
    if(x==father[x]){
        return x;
    }else{
        return father[x]=find(father[x]);
    }
}
void merge(int x,int y){
    ll p=find(x);
    ll q=find(y);
    if(p!=q){/*两个不是一个父节点*/
        father[p]=q;
    }
}
int main(){
    ll n,m;
    cin>>n/*点*/>>m/*边*/;
    ll ri,rj;
    init();
    for(ll i=0;i<m;i++){
        cin>>ri>>rj;
        merge(ri,rj);
    }
    ll cnt=-1;
    for(ll i=1;i<=n;i++){
        if(i==father[i]){
            cnt++;
        }
    }
    printf("%lld",cnt);
    return 0;
}

 相同类型的题目推荐：hdu、hdu