加边的无向图--并查集

加边的无向图

知识点：并查集

题意：题意简单，给你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;
}

 相同类型的题目推荐：HDU1863、HDU1232

原文链接:https://www.cnblogs.com/blogxsc/p/12672466.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有