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;
}
- Components Unicyclic Beginner AtCoder Contestcomponents unicyclic beginner atcoder contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315