Codeforces Round #479 (Div. 3) E. Cyclic Components

Vivienne ·

更新时间:2024-09-20

· 656 次阅读

E. Cyclic Components

题目链接-E. Cyclic Components
在这里插入图片描述

题目大意
给你nnn个点和mmm条边，求所构成图中单圈环的个数

解题思路
并查集并查集并查集

很明显单圈环每个点的度都为222，所以我们可以用数组cnt[]记录每个点的度，只需要找度为222的点即可如果一条边两个顶点的度都为222，我们可以用并查集判断两点是否在一个子图里用并查集判断两个点父节点是否相同，如果父节点相同，就说明找到了环，ans++记录答案，否则就合并具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
//#pragma GCC diagnostic error "-std=c++11"
#include
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair PII;
typedef unsigned long long ull;
int f[N];//记录每个点的父节点
int find(int x){//查找父节点
	return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){//合并
	f[find(x)]=find(y);
}
struct edge{
	int x,y;
}s[N];//记录边
int cnt[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		f[i]=i; //刚开始每个点父节点都是自身
	for(int i=1;i>s[i].x>>s[i].y;
		cnt[s[i].x]++;
		cnt[s[i].y]++;//记录度
	}
	for(int i=1;i<=m;i++){
		if(cnt[s[i].x]==2&&cnt[s[i].y]==2){
			if(find(s[i].x)==find(s[i].y))//查询父节点
				ans++;
			else
				merge(s[i].x,s[i].y);//合并
		}
	}
	cout<<ans<<endl;
	return 0;
}

作者：Fiveneves

CodeForces round div

1024 个赞