欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

加边的无向图--并查集

程序员文章站 2022-03-25 18:55:57
加边的无向图 知识点:并查集 题意:题意简单,给你n个点,m条边,要你求至少要在这个的基础上加多少条无向边使得任意两个点可达。 题解:并查集裸题,直接套用模板即可。 代码: #include #include #include #defin ......

加边的无向图

知识点:并查集

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