CF771A Bear and Friendship Condition 题解
算法
并查集,图的基本性质
分析
题目意思是,一旦有一些点联通,那么这些点必须两两直接相连。换句话讲,就是图中的每个联通块都是完全图。
所谓完全图,就是图中的每个点都两两相连,假设一个完全图有 \(n\) 个点,那么我们可以通过乘法原理算出这个完全图的边数为 \(\frac{n\times(n-1)}{2}\)。那么我们现在只需要用并查集统计一下联通块个数,顺便统计一下每个联通块的点数,算出来所有完全图的边数之和与 \(m\) 比较即可。
注意要开 long long
。
示例代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace Ryan
{
const int N=150005;
int n,m;
int fa[N],sum[N],vis[N];
int find(int x)
{
return (x==fa[x]?x:fa[x]=find(fa[x]));
}
void merge(int x,int y)
{
int ff=find(x);
int fy=find(y);
fa[ff]=fy;
sum[fy]+=sum[ff];
return;
}
signed work()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i,sum[i]=1;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(find(x)!=find(y))
merge(x,y);
}
int k=0,ans=0;
for(int i=1;i<=n;i++)
{
int x=find(i);
if(vis[x])continue;
vis[x]=1;
k+=sum[x]*(sum[x]-1)/2;
ans++;
}
if(k==m)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
return Ryan::work();
}
标签:联通,int,题解,long,fa,Friendship,find,Condition
From: https://www.cnblogs.com/RyanAdam/p/18338488