CF434D: Wizard's Tour

http://codeforces.com/contest/860/problem/D

解いたあとだとめっちゃ自明に見えるけどかなり苦労した。

dfs木を作った後、2辺ずつ木の下からとっていく。
ある点vを中間の点としたpathがとれるときはとる。
取れない場合はvの親pに向かう辺(v,p)を残す。
そうすると、結局M本辺があれば[M/2]個のpathが取れるので最大。

まず無向グラフに使える作戦はdfs木orUnionFind(マージテク含む)くらいしかないことを忘れていた。
dfs木を作った後も、dfsで一番使える情報は、子からの情報だというのに、上から(親の方から)考えようとして詰まった。

int N, M;
bool used[MAX_N];
vector<int> G[MAX_N];
int depth[MAX_N];
vector<tuple<int, int, int>> ans;

bool dfs(int v, int p, int d) {
	used[v] = true;
	depth[v] = d;
	vector<int> vs;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		if(used[n]) {
			if(depth[n] < depth[v]) vs.pb(n);
		}
		else {
			if(dfs(n, v, d + 1)) vs.pb(n);
		}
	}
	vs.pb(p);
	rep(i, 0, sz(vs) / 2) {
		if(vs[i * 2 + 1] == -1 || vs[i * 2] == -1) continue;
		ans.pb(make_tuple(vs[i * 2], v, vs[i * 2 + 1]));
	}
	return sz(vs) % 2;
}

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	rep(i, 0, N) {
		if(!used[i]) dfs(i, -1, 0);
	}
	cout << sz(ans) << "\n";
	rep(i, 0, sz(ans)) {
		int x, y, z; tie(x, y, z) = ans[i];
		x++; y++; z++;
		cout << x << " " << y << " " << z << "\n";
	}
}