AcWing 3719. 畅通工程
原题链接
简单
作者:
多情剑客无情剑
,
2024-02-26 11:30:40
,
所有人可见
,
阅读 23
#include<bits/stdc++.h>
using namespace std;
// 并查集
int s[100001];
bool st[100001];
int needPath=0;
void init(int n){
for(int i=1;i<=n;i++){
s[i]=-1;
st[i]=false;
}
}
int Find(int a){
int x=a;
while(s[x]>0){
x=s[x];
}
return x;
}
void Union(int root1,int root2){
root1=Find(root1);
root2=Find(root2);
if(root2==root1)return ;
else{
s[root2]=root1;
}
}
int main(){
int n,m;
cin>>n>>m;
init(n);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
Union(a,b);
}
for(int i=1;i<=n;i++){
int root=Find(i);
// cout<<root<<endl;
// if(!st[root]){
// st[root]=true;
// needPath++;
// }
if(s[i]==-1)needPath++;
}
cout<<needPath-1;
}