AtCoder AGC #035 : B - Even Degrees

AGCで7回ぶりに正のレートを得た…。
https://atcoder.jp/contests/agc035/tasks/agc035_b

問題

連結無向グラフが与えられる。
各辺に向きを与えたとき、各頂点の出次数が偶数となるようにせよ。

解法

全部の辺を、連続する２辺のペアの集合に分けたとする。
各ペアを成す２辺が頂点U-V-Wを結んでいる場合、V→UとV→Wの向きに辺を張れば、Vの出次数は2増える。

よってこの問題は、辺の集合をそのように分割できればよいことが分かった。
後はその例を作ろう。まず前提として辺の数は偶数でなければならない。
逆に偶数であれば必ず構築できる。

DFSをしながら以下の処理を行おう。

• DFS木において、現在の点v以降を再帰的に処理する。
  • もし子頂点c以下の辺の本数が奇数なら、c以下で1本辺があまる。これは(このDFSの処理に従うなら)必ずcを端点とする辺があまるので、v-cとペアにすればよい。
  • 逆にc以下の辺の本数が偶数なら、v-cは余らせておこう。ほかの辺v-c'に余りが出たらv-cとv-c'をペアにすればよい。

int N,M;
multiset<int> E[101010];
vector<pair<int,int>> V;

int dfs(int cur,int pre) {
	int lef=-1;
	while(E[cur].size()) {
		int x=*E[cur].begin();
		E[cur].erase(x);
		E[x].erase(cur);
		int y=dfs(x,cur);
		
		if(y!=-1) {
			if(lef==-1) lef=y;
			else {
				V.push_back({cur,lef});
				V.push_back({cur,y});
				lef=-1;
			}
		}
	}
	
	if(lef!=-1) {
		if(pre!=-1) {
			V.push_back({cur,pre});
			V.push_back({cur,lef});
			return -1;
		}
	}
	return cur;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x].insert(y);
		E[y].insert(x);
	}
	if(M%2) return _P("-1\n");
	
	dfs(1,-1);
	FORR(v,V) cout<<v.first<<" "<<v.second<<endl;
	
}

まとめ

苦戦しつつも４完は確保できてよかった。