加边的无向图–并查集

0
10

加边的无向图

知识点:并查集

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

<

发布回复

请输入评论!
请输入你的名字