一部ロシアンゲーと呼ばれていた問題。
「問題文がわかりにくい」と評判のなか、問題文は理解できたけど解けませんでした。
http://codeforces.com/contest/528/problem/C
問題
N頂点とM無向辺からなるグラフがある。
このグラフは自己ループや多重辺も認められる。
これらの辺をそれぞれ有向辺にしたい。
その時、各頂点から出る辺の根本及び各頂点に入る辺の根本それぞれを2本ずつペアにして結びたい。
すなわち、全ての頂点の入次数及び出次数を偶数にしたい。
既存の辺で条件を満たせない場合、辺を追加しても良い。
条件を満たす追加辺の数が最小なものを1つもとめ、各有向辺を出力せよ。
解法
長さが偶数の(無向辺)オイラー閉路A-B-C-D-E-F-...があるとする。
これをA→B←C→D←E→F←...と向きが逆の辺が交互に並ぶような有向辺に置き換えれば、条件を満たす有向辺群が作れる。
そのため、以下の手順を行えばよい。
- 各頂点の次数を求め、奇数のものがあれば辺を追加して全部偶数にする。
- 無向辺のオイラー閉路を求める。
- オイラー閉路の長さが奇数なら、適当に自己ループを追加して偶数にする。
- 上記のとおり向きが交互の有向辺として結果を出力する。
template<int MV> class UndirectedEulerPath { public: vector<int> path; multiset<int> E[MV]; void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); } void dfs(int cur) { while(E[cur].size()) { int tar=*E[cur].begin(); E[cur].erase(E[cur].begin()); E[tar].erase(E[tar].find(cur)); dfs(tar); } path.push_back(cur); } bool GetPath() { int fo=-1,odd=0,i,np=0; FOR(i,MV) { np += E[i].size(); if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo; } if(odd!=0 && odd!=2) return false; dfs(odd?fo:0); reverse(path.begin(),path.end()); return path.size()==np/2+1; } }; int N,M; int in[101000]; multiset<int> E[101000]; UndirectedEulerPath<101000> uep; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; x--,y--; if(x>y) swap(x,y); E[x].insert(y); in[x]++; in[y]++; } int odd=-1; FOR(i,N) if(in[i]%2) { if(odd==-1) odd=i; else E[odd].insert(i), in[i]++, in[odd]++, odd=-1; } FOR(i,N) FORR(r,E[i]) uep.add_path(i,r); uep.GetPath(); vector<int> V=uep.path; if(V.size()%2==0) V.push_back(*V.begin()); _P("%d\n",V.size()-1); FOR(i,V.size()-1) { if(i%2) _P("%d %d\n",V[i]+1,V[i+1]+1); else _P("%d %d\n",V[i+1]+1,V[i]+1); } }
まとめ
本番、向きを逆にした有向辺をつなげるのは思いついたけど、オイラー閉路に至れなかった。
これは解法が面白いね。