CS Academy 061 F. Xor the Graph
CS Academy 061 F. Xor the Graph
解法
これを読んでいるとこの解法がかなり自然に見えます。
まず明らかに同じ辺を3回以上使うメリットはありません。そのような構造は、パスの個数を増やすことなく、パスの長さを小さくできるからです。
すべての辺の数字を0にするためには、もともと0と書かれている辺には偶数回、もともと1と書かれている辺には奇数回の操作を施さなければいけません。上に述べた性質から各辺に対して高々2回の操作しか行わないので、もともと1と書かれた辺は1回だけ通ることが言えます。
一方、もともと0と書かれている辺は、0回または2回通ればよいことになるのですが、必ず2回通らなければいけないものとして考えてよいです。なぜなら、「0回通る」を「通ってすぐに戻る」という操作に置き換えることができるからです。
ここまで考察すると、0と書かれた辺は二重にすればよさそうであることがわかります。すると、いくつかのパスによって、すべての辺をただ一度使うようにする問題に変わります。以下、各連結成分ごとに考えます。
もし奇数次の頂点がなければそのグラフはオイラーグラフなので、一つの(単純とは限らない)パスによってすべての辺をただ一度使うことができるので、それを出力します。
奇数次の頂点が存在すれば、その頂点数は偶数個なので、それらの頂点同士をてきとうに結んでしまって、オイラーグラフにしてしまってから、勝手に結んだ辺を切るようにしてパスを作っていけばよいです。ただしこの方法で得られたパスの、最初のパスと最後のパスは繋げて一つのパスとして考えます。
さて、このパスの個数が最小であることを示します。まず、奇数次の頂点が2個存在するとき、それらはあるパスの端点になっていなければいけません(そうでなければ次数を2増やすことになるからです)。よって(奇数次の頂点の個数)/ 2個のパスが最低でも必要です。ところで上の方法によって得られるパスの個数は、切る部分が(奇数次の頂点の個数)/ 2個あるので、(奇数次の頂点の個数)/ 2 + 1個ですが、最初のパスと最後のパスは繋げるので結局(奇数次の頂点の個数)/ 2個のパスで抑えられているので、最小性が言えました。
最後に、0が書かれた辺だけの連結成分が存在する場合は、そこにパスを作っても意味がないので、無視することに注意します。
実装
#include <cstdio> #include <vector> #include <set> #include <cassert> #include <algorithm> #include <functional> using namespace std; //隣接リスト //gを破壊する vector<int> EulerianTrail(const int s, vector<vector<int>> &g, const bool directed, vector<char> &used) { function<void (int, vector<int> &)> dfs = [&](int u, vector<int> &trail) { used[u] = 1; while (!g[u].empty()) { int v = g[u].back(); g[u].pop_back(); if (!directed) { for (int i = 0; i < g[v].size(); i ++) { if (g[v][i] == u) { g[v].erase(g[v].begin() + i); break; } } } dfs(v, trail); } trail.push_back(u); }; vector<int> trail; dfs(s, trail); //reverse(trail.begin(), trail.end()); return trail; } int main() { int n, m; scanf("%d%d", &n, &m); vector<vector<int>> g(n); vector<vector<int>> zero(n); for (int i = 0; i < m; i ++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a --, b --; g[a].push_back(b); g[b].push_back(a); if (c == 0) { g[a].push_back(b); g[b].push_back(a); zero[a].push_back(b); zero[b].push_back(a); } } vector<int> odd; for (int i = 0; i < n; i ++) if (g[i].size() & 1) odd.push_back(i); int oddcnt = odd.size(); set<pair<int, int>> created; for (int i = 0; i < oddcnt; i += 2) { int a = odd[i], b = odd[i + 1]; g[a].push_back(b); g[b].push_back(a); created.insert(make_pair(min(a, b), max(a, b))); } vector<char> used(n, 0); vector<vector<int>> all; for (int i = 0; i < n; i ++) { if (!used[i]) { auto trail = EulerianTrail(i, g, false, used); all.push_back(trail); } } for (int i = 0; i < all.size(); i ++) { bool ok = false; for (int j = 0; j < all[i].size() - 1; j ++) { int a = all[i][j], b = all[i][j + 1]; if (find(zero[a].begin(), zero[a].end(), b) == zero[a].end()) ok = true; } if (!ok) all.erase(all.begin() + i); } vector<vector<int>> ans; for (auto &trail : all) { vector<int> tmp; int first = -1; for (int i = 0; i < trail.size() - 1; i ++) { int a = trail[i], b = trail[i + 1]; tmp.push_back(trail[i]); if (created.count(make_pair(min(a, b), max(a, b)))) { created.erase(make_pair(min(a, b), max(a, b))); if (first == -1) first = (int) ans.size(); ans.push_back(tmp); tmp.clear(); } if (i + 1 == trail.size() - 1) { tmp.push_back(trail[i + 1]); if (ans.size() > 0) { int a = ans[first][0], b = tmp.back(); if (created.count(make_pair(min(a, b), max(a, b)))) { ans.push_back(tmp); } else { for (int j = 1; j < ans[first].size(); j ++) { tmp.push_back(ans[first][j]); } ans[first] = tmp; } } else { ans.push_back(tmp); } } } } printf("%d\n", (int) ans.size()); for (auto trail : ans) { printf("%d ", (int) trail.size()); for (int i = 0; i < trail.size(); i ++) { printf("%d%c", trail[i] + 1, (i == trail.size() - 1 ? '\n' : ' ')); } } }