CF Round #296 Div.1 C. Data Center Drama

Codeforces Round #296 Div.1 C. Data Center Drama

オイラー路の問題をまとめて解いている。
Problem - C - Codeforces

n頂点、m辺の無向グラフが与えられる。各頂点について、その頂点から出ていく本数とその頂点に入ってくる本数がともに偶数になるように、辺の向きを構成し、必要に応じて最小限の数だけ有向辺を追加すると言う問題。オイラー路を使うとわかっている状況で解いたものの、自力でACまで持ち込めた。

まず、各頂点の次数をカウントし、それが奇数のものを列挙し、それらを適当に（てきとーでよいことがあとからわかる）無向辺で繋ぐ。列挙された頂点の数が奇数であることはないので、すべてうまくマッチングされる。なぜなら、グラフにおいて辺を一つ増やすとき必ず全体の次数の総和は２増えるため、ある頂点の次数が奇数であるならば、それに対応するようにまた別のある点が存在して、その次数が奇数であるからである。次数が偶数でなければ条件を満たすことはできないので、これらの辺はどれも必ず作る必要がある。

以上の操作によってできる無向グラフは、全ての頂点の次数が偶数になっているので、任意の点からオイラー閉路が構成可能である。その点を0として、そこから例のオイラー路をつくるアルゴリズムを無向グラフ用に改良して、オイラー路を一つつくる

void visit(int s, vi& path) {
        while (!g[s].empty()) {
                int next = g[s].back();
                g[s].pop_back();
                rep(j, sz(g[next])) {
                        if (g[next][j] == s) {
                                g[next].erase(g[next].begin() + j);
                                break;
                        }
                }
                visit(next, path);
        }
        path.pb(s);
}

これで構成したオイラー路について、そのパスの偶数番目の辺は、オイラー路の向きそのままの向きの有向辺、奇数番目の辺をオイラー路の向きとは逆向きの有向辺として繋いでいく。すると、そのパスが頂点を通るたびに、出ていく辺または入っていく辺のいずれかが２本増加することになり、条件に反しないように有向辺を構成していくことができる。これはオイラー路なので、全ての辺を経由することも保証されている。次数がもともと奇数だった頂点同士をてきとーに繋いでよかったのは、結局オイラー路が構成できるような状態に持ち込んだ時点で、あと問題になるのは辺の数のみになっていたので、どれとどれを繋いでもよかったということである。以上の操作を終えたら、あとは頂点０について条件に矛盾しないようにすればよい。辺の向きは交互に変えて構成していくので、辺の数が偶数であるとき、頂点０についても条件を満たし、これで操作は終わりである。辺の数が奇数であるときは、０から出る辺と０に入る辺の数がともに奇数となっているはずなので、０に自己辺を張ることで条件を満たすようにできる。これらの操作数が最小であることは上にも述べたとおりであるから、これで終わりである。

ちなみにこの実装では、std::cinを使うとTLEとなる。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.14159265358979;

//#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; scanf("%d", &_x); return _x; }
      
vi g[101010];

void visit(int s, vi& path) {
        while (!g[s].empty()) {
                int next = g[s].back();
                g[s].pop_back();
                rep(j, sz(g[next])) {
                        if (g[next][j] == s) {
                                g[next].erase(g[next].begin() + j);//無向グラフなので、反対も壊す
                                break;
                        }
                }
                visit(next, path);
        }
        path.pb(s);
}
        
signed main() { 
        int n, m;
        cin >> n >> m;
        rep(i, m) {
                int a = in(), b = in();
                a --, b --;
                g[a].pb(b);
                g[b].pb(a);
        }
        vi odd;
        rep(i, n) if (sz(g[i]) & 1) odd.pb(i);
        int cnt = 0;
        rep(i, sz(odd)) {
                g[odd[i]].pb(odd[i + 1]);
                g[odd[i + 1]].pb(odd[i]);
                i ++;
                cnt ++;
        }
        vi path;
        visit(0, path);
        reverse(all(path));
        vpii ans;
        rep(i, sz(path) - 1) {
                if (i & 1) ans.pb(mp(path[i], path[i + 1]));
                else ans.pb(mp(path[i + 1], path[i]));
        }
        if ((m + cnt) & 1) ans.pb(mp(0, 0));
        cout << sz(ans) << endl;
        rep(i, sz(ans)) cout << ans[i].fi + 1 << ' ' << ans[i].se + 1 << endl;
        return 0;
}               

オイラー路の応用範囲は広そうだ。おもしろい問題も多い印象。