AtCoder Beginner Contest 292 D - Unicyclic Components

发布时间 2023-09-01 13:08:35作者: 无上大宗师

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;
}