题解：AT_abc404_c [ABC404C] Cycle Graph?

· · 题解

认真读一遍题

这道题就是判断一个简单无向图是否能构成题目定义的环，这个环有要求。

  1. 整一个图从一个点开始可以通过边按一定顺序不重复走完图中所有的点且回到原点。
  2. 没有多余的边。

第二个条件就很简单了，题目保证无重边无自环，从一个点开始能经过n的点且绕回原点必然经过了 n 条边，所以如果 n \ne m 则必然无法走 n 个点或有多余的边。

至于满足第一个条件，我们发现如果能画出这样的一个环，每一个点的度必然为2。

证明：

  1. 不可能存在度为0的点，因为走不到
  2. 不可能存在度为1的点，因为走到了回去会重复经过一个点
  3. 不可能存在度比2大的点，我们已经限制边的数量为 n ，所以存在时必然存在前两点的点

所以判定一个环，只需要所有点入度为2即可（先卖个罐子，这个判定还不全）

#include <bits/stdc++.h>
using namespace std;
int d[200010];
int n, m;
bool f;
int main()
{
    cin >> n >> m;
    if (n != m) { fputs("No", stdout);return 0; }
    static int u, v;
    for (int i = 1;i <= m;i++) cin >> u >> v, d[u]++, d[v]++;
    for (int i = 1;i <= n;i++)
        if (d[i] != 2)
            return (fputs("No", stdout), 0);
    fputs("Yes", stdout);
    return 0;
}

提交，发现在atcoder上WA了4个点。

为什么呢？

思考一下，对于一个图，如果它由题意要求能分割为多个环，那么依旧符合我们的判定条件，所以所有点都要联通。无向图联通问题，只需要一个并查集就能解决。

#include <bits/stdc++.h>
using namespace std;
int d[200010];
int n, m;
bool f;
int fa[200010];
int ff(const int& x)
{
    if (x == fa[x]) return x;
    return fa[x] = ff(fa[x]);
}
int main()
{
    cin >> n >> m;
    if (n != m) { fputs("No", stdout);return 0; }
    for (int i = 1;i <= n;i++) fa[i] = i;
    static int u, v;
    for (int i = 1;i <= m;i++) cin >> u >> v, d[u]++, d[v]++, fa[ff(u)] = ff(v);
    for (int i = 1;i <= n;i++)
        if (d[i] != 2 || ff(1) != ff(i))
            return (fputs("No", stdout), 0);
    fputs("Yes", stdout);
    return 0;
}