Codeforces #296 Div1 C. Data Center Drama

一部ロシアンゲーと呼ばれていた問題。
「問題文がわかりにくい」と評判のなか、問題文は理解できたけど解けませんでした。
http://codeforces.com/contest/528/problem/C

問題

N頂点とM無向辺からなるグラフがある。
このグラフは自己ループや多重辺も認められる。

これらの辺をそれぞれ有向辺にしたい。
その時、各頂点から出る辺の根本及び各頂点に入る辺の根本それぞれを２本ずつペアにして結びたい。
すなわち、全ての頂点の入次数及び出次数を偶数にしたい。

既存の辺で条件を満たせない場合、辺を追加しても良い。
条件を満たす追加辺の数が最小なものを１つもとめ、各有向辺を出力せよ。

解法

長さが偶数の(無向辺)オイラー閉路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);
	}
}

まとめ

本番、向きを逆にした有向辺をつなげるのは思いついたけど、オイラー閉路に至れなかった。
これは解法が面白いね。