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"; } }