CF977E

FiraCode · 2022-10-02 09:53:08 · 题解

题解思路：

我们先用并查集来维护连通块，然后再判断每个联通块是否是环即可。

那么判断是否是环，我们就看看他每个点的度数是否都为 2 就可以了。

那么再读入边的时候我们就维护一下并查集还有每个点的度数，那么当一个点的度数不为 2 的时候，就把他所在的集合标记一下。

然后最后遍历一下所有的集合，看看是否标记就可以了。

AC CODE：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int p[200010];
int du[200010];
bool st[200010];
int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)//初始化并查集
        p[i] = i;
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (find(a) != find(b))
            p[find(a)] = find(b);//预处理并查集
        du[a] ++; du[b] ++;//度数+1
    }
    for (int i = 1; i <= n; ++i) {
        if (du[i] != 2) {//不满足条件
            st[find(i)] = true;//标记一下
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i)
        if (p[i] == i && !st[i])//是环
            res ++;//答案++
    printf("%d\n", res);
    return 0;
}