实在不行出个HACK也好啊
by ABCgfed @ 2023-05-29 23:14:51
@[ABCgfed](/user/764239) 这是我以前写的用并查集写的
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int fa[N],n,m,p,q,ans=1e6,cnt;
// 初始化并查集
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i;
}
// 查找x所在的集合 + 路径压缩
int find_Set(int x) {
if (fa[x] != x) fa[x]=find_Set(fa[x]);
return fa[x];
}
// 合并x和y所在的集合，并且把他们的父节点赋值为小的那个
void merge(int x, int y){
int fx = find_Set(x);
int fy = find_Set(y);
if (fx < fy) fa[fy] = fx;
else fa[fx] = fy;
}
int main(){
while(scanf("%d",&n)&&n){
int a,b,ans=0;
scanf("%d",&m);
init(n);
while(m--) scanf("%d%d",&a,&b),merge(a,b);
for(int i=1;i<=n;i++)
if(find_Set(i)!=1) ans++,merge(1,i);
printf("%d\n",ans);
}
return 0;
}
```
by uberking @ 2023-05-29 23:30:20
推荐使用并查集捏
by Rebirth_Yun @ 2023-07-22 19:44:53