AcWing 3719. 畅通工程
原题链接
简单
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e4+10;
int t,n,m,k,l,r,op,x,y,a,b,cnt;
int f[N];
bool flag;
int find(int x){
if(x==f[x])return x;
return find(f[x]);
}
void merge(int x,int y){
x = find(x);
y = find(y);
if(x<y)swap(x,y);
f[x] = y;
}
void solve(){
cin>>n>>m;
for(int i = 1;i<=n;i++){
f[i] = i;
}
for(int i = 1;i<=m;i++){
cin>>a>>b;
merge(a,b);
}
for(int i = 1;i<=n;i++){
if(f[i]==i)cnt++;
}
cout<<cnt-1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}