并查集（大裸题）

给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达~

4 2
1 2
3 4

1

居然一开始看到没有立马想到并查集，ans=联通区域数-1；

ACCODE:

#include
using namespace std;
int fa[100010];
int n,m;
int find(int x){
    if(x==fa[x])return x;
    else return
        fa[x]=find(fa[x]);
}
void merge(int a,int b){
    fa[find(a)]=find(b);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1,a,b;i<=m;i++){
        cin>>a>>b;
        merge(a,b);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i)cnt++;
    }
    cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5699435.html