加边的无向图–并查集

加边的无向图

知识点:并查集

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

 

https://www.cnblogs.com/blogxsc/p/12672466.html

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论