题解：AT_abc404_c [ABC404C] Cycle Graph?

题目大意

有

N

个点与

M

条边，让你求它是不是有且仅有一个的循环图。

思路

首先判断图是否联通，如果不连通就不符合题意，无解。
其次考虑 $n$ 个点是不是组成了一个环，我们只需要判断每个点的度数是否都为 $2$ ，因为如果一个点的度数为 $1$ ，肯定不在环里，度数大于 $2$ ，则一定不能只组成一个环。

Code

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

int du[N];

int f[N];
int find(int x){
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
/*
	1. 判断给定图，是否联通  dfs  并查集
	2. 判断每个点的度数是不是2

*/
int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) f[i] = i;
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		int fu = find(u), fv = find(v);
		f[fu] = fv;
		du[u]++;
		du[v]++;
	}
	for(int i = 1; i <= n; i++){
		if(find(i) != find(1) || du[i] != 2){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
    return 0;
}

题解：AT_abc404_c [ABC404C] Cycle Graph?

文章操作

题目大意

思路

Code

相关推荐

评论

题解：AT_abc404_c [ABC404C] Cycle Graph?