見るからにコーナーケースが怖い...

問題概要

$N$ 頂点 $M$ 本の辺からなる単純かつ連結な無向グラフが与えられます。

全ての辺をちょうど一回ずつ使って $3$ つのサーキットを作ることが可能かどうかを判定してください。

制約

$1 \le M, N \le 10^{5}$

考えたこと

輪っかを 3 つ作るような問題なのだが、輪っかが何個もある分には問題無い。

のような輪っかが 5 個あるようなグラフであっても、輪っか 3 個で 1 個の輪っかにして、のこり 1 個ずつで合計 3 個のサーキットを作ることができる。

むしろ問題なのは

のようにどんなに頑張っても輪っかが 2 個しか作れないようなグラフを弾くことに本質がある。

さて、とりあえずまず言えるのは

与えられたグラフはそもそも Euler グラフ (一筆書き可能で、一筆書きのスタートに最後戻ってこれる) でなければならない
したがって、すべての頂点の次数は偶数でなければならない

ということ。そしてとりあえず

次数が 6 以上の頂点 v があれば、必ず 3 個の輪っかは作れる

ということは言えそう。厳密には Euler 路によって一筆書きを求めてあげて、v のところで切るようにしてあげれば 3 本のサーキットに分離できるので OK。

次数が 4 以下の頂点しか無い場合

まず次数が 4 以下の頂点が 3 個以上ある場合は必ずできる (公式解法の証明が明快)。

次数が 4 以下の頂点が 1 個だけの場合はできない。

よって問題は次数が 4 以下の頂点が 2 個ある場合に絞られた。

上図のように、できる場合とできない場合がある。できない場合の判定方法は色々あるだろうが、たとえば

「次数 4 の頂点 v から出発して、一度も他の次数 4 の頂点にぶつからずに v に戻ってこれるかどうか」

で判定すればよさそう。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int N, M;
vector<vector<int> > G;

vector<bool> seen;
bool rec(int v, int p, int s, int t) {
    if (v == s && p != -1) return true; // 一周回ってきて s に戻って来たら OK
    if (v != s) seen[v] = true;
    for (auto nv :  G[v]) {
        if (nv == p || nv == t || seen[nv]) continue;
        if (rec(nv, v, s, t)) return true;
    }
    return false;
}
        
bool solve() {
    cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    map<int,int> degs;
    for (int v = 0; v < N; ++v) degs[(int)G[v].size()]++;

    for (auto it : degs) if (it.first % 2 != 0) return false;
    if (degs[6] > 0) return true;
    if (degs[4] > 2) return true;
    if (degs[4] <= 1) return false;

    vector<int> four;
    for (int v = 0; v < N; ++v) if (G[v].size() == 4) four.push_back(v);
    int s = four[0], t = four[1];
    seen.assign(N, 0);
    return rec(s, -1, s, t);
}

int main() {
    if (solve()) cout << "Yes" << endl;
    else cout << "No" << endl;
}