面白い！！！！！！！
問題概要
頂点
辺の無向単純グラフが与えられる (連結とは限らない)。
このグラフに何本かの辺を付け加えることで「連結なオイラーグラフ」にすることができるかどうかを判定し、できるならば一例を示せ。ただし多重辺を作ってはならない。
制約
解法
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 での連立一次方程式を立ててもできるみたい。
