Codeforces #434 Div1 D. Wizard's Tour

これは割とすんなり。
http://codeforces.com/contest/860/problem/D

問題

無向グラフが与えられる。
ここでx-y-zと辺でつながっているような(x,y,z)の組をできるだけ多く作りたい。
同じ辺を複数回に使わないようにして、そのような組を構築せよ。

解法

各連結成分について処理していく。
このような3つの点の組を作るというのは、結局連結した２つの辺の組を作っていくこととと等しい。

そこで、同じ辺を２回使わないようにして辺をDFSする。
子頂点に至る辺で余った辺が出たら適宜組み合わせていこう。
余った辺が奇数の場合、親方向の辺と組み合わせる。
そうでない場合、親方向の辺が余るので、親のDFSのときに「余った辺」として再帰的に処理していくとよい。

int N,M;
vector<int> E[202020];
map<pair<int,int>,int> EE;
int vis[202020];
int vise[202020];
vector<vector<int>> R;

int dfs(int cur,int pre) {
	int m=-1;
	if(vis[cur]) return cur;
	vis[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		if(vise[EE[{cur,e}]]) continue;
		vise[EE[{cur,e}]]=1;
		int tar=dfs(e,cur);
		if(tar!=-1) {
			if(m==-1) {
				m=tar;
			}
			else {
				R.push_back({m,cur,tar});
				m=-1;
			}
		}
	}
	
	if(m==-1) {
		return cur;
	}
	else {
		if(pre!=-1) R.push_back({m,cur,pre});
		return -1;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
		EE[{x,y}]=EE[{y,x}]=i;
	}
	FOR(i,N) if(vis[i+1]==0) dfs(i+1,-1);
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d %d %d\n",r[0],r[1],r[2]);
	
}

まとめ

これ普段のDiv1 2000ptよりは簡単な気がする。