Fの方が簡単?
http://codeforces.com/contest/723/problem/E
問題
無向グラフが与えられる。
各辺に向きを付け有向グラフにしたい。
その際、入次数と出次数が等しい頂点数を最大にしたい。
最大で何頂点そのような点を作れるか。また、その際の辺の向きを答えよ。
解法
全頂点が連結で、かつ次数が偶数ならオイラー閉路を求めれば全頂点で条件を満たせる。
元のグラフに辺を足し、そのような形状にしよう。
とはいえ手順は簡単で、次数が奇数の点が偶数個あるはずなので、まずそれらを2つずつ対にして辺を1個追加しよう。
また、グラフが非連結の場合、例えば0番の頂点と非連結な連結成分があれば、0番の頂点と後者の連結成分の1頂点の間に2本辺を張ろう。
後はこの状態のグラフに対しオイラー閉路を求めればよい。
元の次数が奇数個の点は条件を満たせないが、それ以外の頂点は入次数と出次数が等しくなる。
template<int um> class UF { public: vector<int> par,rank; UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; 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; } }; void solve() { int i,j,k,l,r,x,y; string s; int T,N,M; cin>>T; while(T--) { int mat[203][203]={}; int E[203]={}; ZERO(mat); UF<220> uf; cin>>N>>M; int ret=N; UndirectedEulerPath<205> uep; FOR(i,M) { cin>>x>>y; x--; y--; mat[x][y]=mat[y][x]=1; E[x]++; E[y]++; uf(x,y); uep.add_path(x,y); } int pre=-1; FOR(i,N) if(uep.E[i].size()%2==1) { ret--; if(pre==-1) { pre=i; } else { uep.add_path(pre,i); uf(pre,i); pre=-1; } } FOR(i,N) if(uf[i]!=uf[0]) { uep.add_path(0,i); uep.add_path(0,i); uf(0,i); } uep.GetPath(); _P("%d\n",ret); FOR(i,(int)uep.path.size()-1) { if(mat[uep.path[i]][uep.path[i+1]]) { _P("%d %d\n",uep.path[i]+1,uep.path[i+1]+1); mat[uep.path[i]][uep.path[i+1]]=mat[uep.path[i+1]][uep.path[i]]=0; } } } }
まとめ
入次数=出次数、という条件が出たらオイラー閉路を疑おう。