Codeforces Round #375 (Div. 2): E. One-Way Reform

,

http://codeforces.com/contest/723/problem/E

solution

奇数次数の頂点の間に適当に辺を張り全て偶数次数にし、辺集合を適当に閉路に分割し、それぞれの閉路を勝手に有向閉路化すればよい。奇数次数の頂点の間に張った辺は出力の際には取り除く。$O(N^3)$。

答えの整数は偶数次数の頂点数を越えないことは明らか。 上の手順で全ての偶数次数の頂点が、入次数と出次数が等しいものになることを確認すればよい。 これは有向閉路上の頂点ということから言える。

implementation

#include <cstdio>
#include <vector>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

pair<int, vector<pair<int, int> > > solve(int n, vector<vector<int> > const & g) {
    vector<vector<bool> > is_original = vectors(n, n, false); // adjacency matrix
    repeat (i,n) for (int j : g[i]) is_original[i][j] = true;
    vector<vector<int> > h = vectors(n, n, 0); // adjacency matrix
    repeat (i,n) for (int j : g[i]) h[i][j] += 1;
    vector<bool> used(n); // of vertices
    vector<pair<int, int> > result;
    repeat (root,n) if (not used[root]) {
        // split to components
        vector<bool> connected(n);
        function<void (int)> connect = [&](int i) {
            used[i] = true;
            connected[i] = true;
            for (int j : g[i]) if (not used[j]) {
                connect(j);
            }
        };
        connect(root);
        // connect odd-degree vertices
        vector<int> odds;
        repeat (i,n) if (connected[i]) {
            if (g[i].size() % 2 == 1) {
                odds.push_back(i);
            }
        }
        assert (odds.size() % 2 == 0);
        repeat (k, odds.size() / 2) {
            int i = odds[2*k  ];
            int j = odds[2*k+1];
            h[i][j] += 1;
            h[j][i] += 1;
        }
        // orient edges
        function<void (int, int)> orient = [&](int i, int j) {
            if (is_original[i][j]) {
                result.emplace_back(i, j);
                is_original[i][j] = false;
                is_original[j][i] = false;
            }
            h[i][j] -= 1;
            h[j][i] -= 1;
        };
        function<void (int, int)> go = [&](int i, int root) {
            repeat (j,n) if (h[i][j]) {
                orient(i, j);
                if (j != root) {
                    go(j, root);
                }
                return;
            }
            assert (false);
        };
        repeat (i,n) if (connected[i]) {
            repeat (j,n) while (h[i][j]) {
                orient(i, j);
                go(j, i);
            }
        }
    }
    int cnt = 0;
    repeat (i,n) cnt += (g[i].size() % 2 == 0);
    return make_pair(cnt, result);
}

int main() {
    int t; scanf("%d", &t);
    while (t --) {
        int n, m; scanf("%d%d", &n, &m);
        vector<vector<int> > g(n);
        repeat (i,m) {
            int u, v; scanf("%d%d", &u, &v); -- u; -- v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int cnt; vector<pair<int, int> > result; tie(cnt, result) = solve(n, g);
        printf("%d\n", cnt);
        for (auto e : result) {
            int i, j; tie(i, j) = e;
            printf("%d %d\n", i+1, j+1);
        }
    }
    return 0;
}