AcWing 5557. 孤立点数量
原题链接
困难
作者:
最后五分钟
,
2024-03-17 02:31:41
,
所有人可见
,
阅读 17
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int p[N],st[N];
int find(int x)
{
if(p[x]!=x)return p[x]=find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
a=find(a),b=find(b);
if(a!=b)
{
p[b]=a;
st[a]|=st[b];
}
else st[a]=1;
}
int res=0;
for(int i=1;i<=n;i++)
if(p[i]==i&&!st[i])res++;
cout<<res<<endl;
return 0;
}
你好,问个问题,如果有重边是不是会误判为环
会的,虽然题目保证没有重边,但即使有重边,重边构成的环所在的连通块内仍然可以构造不存在孤立点的方案
谢谢啦