题目链接
$\color{blue}{Acwing3719.畅通工程}$
算法1
并查集
统计连通块的个数 $res$ ,输出 $res - 1$ ,,可以用并查集实现
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N];
int Find(int x){
if(p[x]!=x)p[x] = Find(p[x]);
return p[x];
}
void Union(int x,int y){
int a = Find(x);
int b = Find(y);
if(a!=b)p[b] = a;
}
int main(){
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++)p[i] = i;
for(int i = 0;i<m;i++){
int x,y;cin>>x>>y;
Union(x,y);
}
int res = 0;
for(int i = 1;i<=n;i++)if(p[i]==i)res++;
printf("%d\n",res-1);
return 0;
}