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' : ' '));
                }
        }
}