题意

图上有 n 个点，m 条无向边，问要在建几条边使得图连通。

思路

用并查集来做，统计连通块个数 k，答案为 k−1，不知道并查集是什么的点这里 并查集。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m;
int par[maxn],rk[maxn];
set<int> s;
void init(){
    for(int i = 1;i <= n;i++) {
        par[i] = i;
        rk[i] = 0;
    }
}
int find(int x) {
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
}
void unite(int x,int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rk[x] < rk[y]) par[x] = y;
    else{
        par[y] = x;
        if(rk[x] == rk[y]) rk[x]++;
    }
}
signed main(){
    cin >> n >> m;
    init();
    for(int i = 1;i <= m;i++) {
        int x,y;
        cin >> x >> y;
        unite(x,y);
    }
    for(int i = 1;i <= n;i++) 
        s.insert(find(i));
    cout << s.size() - 1;
    return 0;
}