Codeforces #238 Div1 C. Graph Cutting

これは思いつかなかったので他の回答を見て練習。
http://codeforces.com/contest/406/problem/C

問題

N点・M辺からなる無向連結グラフが与えられる。
各辺の長さを1としたとき、同じ端点を共有する2本の辺を連結してM/2本の長さ2の辺を作りたい。
(当然元の辺は長さ2の辺のうち1か所でしか使えないため、全部の辺を1回ずつ使うことになる)

そのような長さ2の辺の配列を返せ。

解法

Mが奇数の時は当然解答なし。
Mが偶数のとき、以下のようにDFSすることで答えられる。

• 各点におけるDFS関数では、もしその点の先に余った辺があればそれを上に返す。なければ無しと返す。
• DFS中、各点ではそこからつながる未使用の辺の先の点をDFSで探索する。
  • もし未使用の辺の先の点に余る辺がある場合、今の辺から先の点に至る辺と、その先の点から先で余る辺を連結して長さ２の辺を作る。
  • もし未使用の辺の先の点に余る辺がない場合、今の辺から先の点に至る辺は余っていることになる。ほかに余っている辺があればそれとつなげて長さ２の辺を作る。
  • 最終的に余った辺があれば、それをDFSの返り値として返す。

int N,M;
vector<pair<int,int> > E[100001];
int vise[100001];
int visv[100001];

int dfs(int cur) {
	int left=-1,i,r;
	visv[cur]=1;

	FOR(i,E[cur].size()) {
		int tar=E[cur][i].first;
		if(vise[E[cur][i].second]) continue;
		vise[E[cur][i].second]=1;
		r=dfs(tar);
		
		if(r==-1) {
			if(left==-1) {
				left=tar;
			}
			else {
				_P("%d %d %d\n",left,cur,tar);
				left=-1;
			}
		}
		else {
			_P("%d %d %d\n",cur,tar,r);
		}
	}
	return left;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(make_pair(y,i));
		E[y].push_back(make_pair(x,i));
	}
	
	if(M%2==1) return _P("No solution\n");
	dfs(1);
}

まとめ

よく考えたら、こういう下での余りを上に伝搬していくDFSはやったことあったな…。
でも本番これを思いつくのはDより無理だったな…。