加边的无向图

思路

并查集找到联通块的个数，答案就是联通块个数减一。

因为这是无向图，所以就不用dfs跑个数了，直接裸的并查集就好了

如果没有学过并查集可以去看看这篇博客，这位大佬写的巨详细

那就直接上代码了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int fa[maxn];
int find(int x){
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void merge(int x,int y){
    int i = find(x);
    int j = find(y);
    fa[i] = j;
}
void init(){
    for(int i = 0 ; i < maxn ; ++i) fa[i] = i ;
}
int main(){
        int n = read(),m = read();
    init();
        for(int i = 1 ; i <= m ; ++i){
            int x = read(),y = read();
            merge(x,y);
        }
        int ans  = 0;
        for(int i = 1 ; i <= n ; ++i){
            if(find(i) == i) ++ans;
        }
        cout<<ans - 1<<endl;
}