AcWing 5557. 孤立点数量
原题链接
困难
作者:
代码人生
,
2024-03-17 09:29:57
,
所有人可见
,
阅读 29
首先本题需要我们发现一些性质:
1.对于基环树来说,一定可以构造一种方案使得孤立点数量为0(构造方案:对于环上的点所对应的树,我们可以将子节点指向根节点)
2.对于一棵树来说,我们可以保证最少有1个孤立点,构造方案与上一个类似
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N];
bool st[N];// 当前所在集合是否有环
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (m -- ){
int a,b;
scanf("%d %d",&a,&b);
a = find(a),b = find(b);
if(a == b) st[a] = true;// 当前集合代表元素的st值为true
else p[a] = b,st[b] |= st[a];// 将A插入到B上
}
int ans = 0;
for (int i = 1; i <= n; i ++ ){
if(p[i] == i && !st[i]){
ans++;
}
}
printf("%d",ans);
return 0;
}