题解 AGC032C Three Circuits

· · 题解

先补一张原题面的样例解释：

很明显的，我们发现对于合法的方案，每个点的度一定为偶数，这也提示我们要对度数分类讨论：

  1. 对于度 \ge 6 的点，至少可以拆成三个环；

  2. 对于度为 4 的点，一定可以拆成两个环；

  3. 对于度为 2 的点，只能拆成一个环。

其实有一个显然的结论：经过同一个点的两个环可以合并，也可以拆分，一个度数为 d 的点可以拆出 \dfrac{d}{2} 个环。

接下来就是如何判断：

  1. 含有奇数度数的点一定不合法；

  2. 含有度数 \ge 6 的点一定合法；

  3. 含有度数为 4 且不含度数 \ge 6的点：

    1. 如果只有一个，一定不合法；

    2. 对于两个点，又可以分成两种情况（如下图），显然左图不合法，右图合法；

    3. 有 \ge 3 个一定合法；

  4. 只有度数为 2 的点，一定不合法。

唯一麻烦的地方在于有两个度为 4 点时的 check，一种比较简单的实现思路是从其中一个点开始 dfs，如果经过另外一个点 4 次，则认为不合法，经过 2 次，认为合法。

代码实现的话也很简单，st[] 记录度为 4 的点，也就是 dfs() 中的起点和终点，cntt 记录路径数，vis[] 记录经过边的编号。

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

struct edge {int to, nxt;} e[maxn<<1];
int cnt = 1, head[maxn];

int n, m, cnt4, cnt6, cntt, deg[maxn], st[2];
bool vis[maxn<<1];

void add(int u, int v) {
    e[++cnt] = {v, head[u]}, head[u] = cnt, deg[u]++;
}

void dfs(int u) {
    for (int i = head[u]; i; i = e[i].nxt) {
        if (e[i].to == st[1]) return cntt++, void();
        if (vis[i]  == 0)
            vis[i] = vis[i^1] = 1, dfs(e[i].to);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i] &  1) return puts("No" ),0;
        if (deg[i] == 4) cnt4++, st[cnt4%2]=i;
        if (deg[i] >= 6) cnt6++;
    }
    if (cnt4 == 2) dfs(st[0]);
    if (cnt6 >= 1) return puts("Yes"), 0;
    if (cnt4 <= 1) return puts("No" ), 0;
    if (cnt4 >= 3) return puts("Yes"), 0;
    if (cntt == 2) return puts("Yes"), 0;
    return puts("No"), 0;
}