NC14685 加边的无向图 [并查集]

题意

一个 n 个点，m 条边的无向图，加边使无向图联通

题解

并查集板子题
使联通的两点union，最后得到x棵树，即无向图的x个连通子图，两两之间填一条边即可得答案为x-1

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int fa[maxn];                   //记录祖先节点

int fi(int x){                  //find函数寻找祖先
    return x == fa[x] ? x : fa[x] = fi(fa[x]);
}

void un(int x,int y){           //union函数建立两点关系
    int p = fi(x);
    int q = fi(y);
    if(p != q) fa[p] = q;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n;++i) fa[i] = i;        //init
    for(int i = 0;i < m;++i){
        int u, v;
        scanf("%d %d",&u,&v);
        un(u,v);
    }

    int cnt = 0;
    for(int i = 1;i <= n;++i){
        if(fa[i] == i) cnt++;               //寻找树根 即子图个数
    }
    printf("%d\n",cnt-1);

    return 0;
}