题解：AT_abc404_c [ABC404C] Cycle Graph?

ZZ0520 · 2025-05-09 09:50:18 · 题解

题目大意

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

思路

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

Code

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