けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1393 Eulerian Flight Tour (ICPC アジア 2018 E)

面白い!!!!!!!

問題へのリンク

問題概要

 N 頂点  M 辺の無向単純グラフが与えられる (連結とは限らない)。
このグラフに何本かの辺を付け加えることで「連結なオイラーグラフ」にすることができるかどうかを判定し、できるならば一例を示せ。ただし多重辺を作ってはならない。

制約

  •  3 \le N \le 100

解法

connected にしないとダメだけど、とりあえずそれを一旦無視して、「すべての頂点の次数が偶数」という状態にできるかどうかを最初に解くことにする。

  • それができなかったら、そもそも "No" となる。
  • それができた場合...

実は、元々の入力グラフが

  • 孤立点 + 次数が奇数の完全グラフ」という入力以外なら必ずできる

ことが示せる。「孤立点 + 次数が奇数の完全グラフ」という入力に対して "No" なのは明らか。

そうでないときに、とりあえず connected かどうかを無視して辺を付け加えて「偶数次数頂点のみの連結成分何個か」になったとする。

  • それが 1 個のとき、すでに connected
  • それが 3 個以上のとき、それぞれから 1 点ずつ選んできて、それらでサイクルを作れば良い
  • それが 2 個のとき
    • 2 つともサイズ 2 以上のとき、蝶々みたいな繋ぎ方をすればいい
    • どちらかが 1 点 w で、もう片方が完全グラフではないとき、もう片方のまだ余っている辺 (u, v) を選んで、w-u-v で三角形を作ればいい
    • どちらかが 1 点 w で、もう片方が完全グラフのとき、入力がそうではないことから「完全グラフの中に付け加えられた辺 (u, v)」があるはずで、それを一旦取り外して (w, u) と (w, v) を付け加えればいい

という風にして構成することができる。

よって残った問題は、「connected かどうかに関係なく、グラフのすべての次数を偶数にできるか?」となる

解法 1

入力されたグラフの補グラフをとる。補グラフを連結成分ごとに分ける。このとき、元のグラフでの次数が奇数の頂点を odd な点と呼ぶことにするとき

  • どの連結成分をとっても、odd な頂点数が偶数個であること

ができるための必要十分条件であることは比較的容易にわかる。odd な頂点数が偶数個であるとき、具体的な構成としては

  • 連結成分の全域木を考える
  • 葉から順に、odd 頂点から親への辺を、元のグラフに追加する (このときその頂点は even 属性になり、親は属性が入れ替わることに注意)

をして行けばよい。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;

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

bool ok = true;
vector<bool> seen;
vector<pint> res;
void rec(int v, int p) {
    seen[v] = true;
    for (int nv = 0; nv < N; ++nv) {
        if (seen[nv]) continue;
        if (G[v][nv]) continue;
        rec(nv, v);
    }
    if (deg[v] & 1) {
        if (p == -1) ok = false;
        else {
            res.push_back(pint(v, p));
            ++deg[v]; ++deg[p];
            G[v][p] = 1; G[p][v] = 1;
        }
    }
}

vector<int> temp;
vector<vector<int> > comp;
void rec2(int v) {
    seen[v] = true;
    for (int nv = 0; nv < N; ++nv) {
        if (nv == v) continue;
        if (seen[nv]) continue;
        if (!G[v][nv]) continue;
        rec2(nv);
    }
    temp.push_back(v);
}

void solve() {
    ok = true;
    seen.assign(N, 0);
    res.clear();
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        rec(v, -1);
    }
    
    // cannot
    if (!ok) {
        cout << -1 << endl;
        return;
    }
    
    // decomposition
    seen.assign(N, 0);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        temp.clear();
        rec2(v);
        comp.push_back(temp);
    }

    // reconstruct
    if (comp.size() == 2) {
        if (comp[0].size() > comp[1].size()) swap(comp[0], comp[1]);
        if (comp[0].size() == 1) {
            int t = comp[0][0];
            int u = -1, v = -1;
            for (int i = 0; i < comp[1].size(); ++i) {
                for (int j = i + 1; j < comp[1].size(); ++j) {
                    int cu = comp[1][i], cv = comp[1][j];
                    if (!G[cu][cv]) u = cu, v = cv;
                }
            }
            if (u == -1) {
                if (res.size() == 0) {
                    cout << -1 << endl;
                    return;
                }
                u = res.back().first;
                v = res.back().second;
                res.pop_back();
            }
            else {
                res.push_back(pint(u, v));
            }
            res.push_back(pint(t, u));
            res.push_back(pint(t, v));
        }
        else {
            for (int it = 0; it < 2; ++it) {
                for (int it2 = 0; it2 < 2; ++it2) {
                    res.push_back(pint(comp[0][it], comp[1][it2]));
                }
            }
        }
    }
    else if (comp.size() > 2) {
        for (int i = 0; i < comp.size(); ++i) {
            int j = (i + 1) % comp.size();
            res.push_back(pint(comp[i][0], comp[j][0]));
        }
    }
    
    // output
    cout << res.size() << endl;
    for (auto &p : res) {
        if (p.first > p.second) swap(p.first, p.second);
        cout << p.first + 1 << " " << p.second + 1 << endl;
    }
}

int main() {
    cin >> N >> M;
    G.assign(N, vector<bool>(N, 0));
    deg.assign(N, 0);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a][b] = G[b][a] = 1;
        deg[a]++; deg[b]++;
    }
    solve();
}

解法 2

mod. 2 での連立一次方程式を立ててもできるみたい。