Codeforces Round #375 (Div. 2): E. One-Way Reform
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;
}