AtCoder Beginner Contest 292 D - Unicyclic Components
D - Unicyclic Components
原题链接
题意：判断一个连通块的边和点个数是否相同
思路：对它使用并查集吧
#include <bits/stdc++.h>
using namespace std;
const int N = 200010,M=N<<1;
//维护连通图中点和边的个数
int sd[N],se[N],p[N];
bool f[N];//谁是祖宗
int n,m;
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<N;i++)
{
p[i]=i,sd[i]=1,se[i]=0,f[i]=1;
}
while(m--)
{
int u,v;
cin>>u>>v;
int pa=find(u),pb=find(v);
if(pa!=pb)
{
f[pa]=0;
f[pb]=1;
p[pa]=pb;
sd[pb]+=sd[pa];
se[pb]+=se[pa]+1;
}
else
{
se[pb]+=1;
}
}
for(int i=1;i<=n;i++)
{
if(f[i]==1)
{
if(se[i]!=sd[i])
{
cout<<"No\n";
return 0;
}
}
}
cout<<"Yes\n";
return 0;
}