TopCoder SRM 766 : Div1 Medium BannedBook

これはすんなり解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=15699

問題

N人の人の間で１回ずつ本を回す。(最後に回した人は最初の人に戻さなくてよい）。
ここで、各人の友人関係が与えられる。

人の間で本を渡すとき、両者が友人・友人の友人・友人の友人の友人のいずれかならリスクが無く、そうでない場合リスクが高い。
本の回し方のうち、リスクの高い受け渡し回数が最小となるケースを１つ答えよ。

解法

人を頂点、友人関係を辺で表したグラフを考える。
各連結頂点内を、リスクの無い受け渡しで全員回す手段がわかれば、リスクの高い受け渡しは連結頂点じゃないもの同士の受け渡しだけとなり、これは明らかに最小である。

さて、連結頂点内で、距離３以下の移動を繰り返し、全頂点を１回ずつ訪問する訪問順があればよいことになる。
これは連結木のDFS木において、根からの距離が偶数の点は行き掛け、奇数の点は帰りがけに訪問するようにすると、これを満たす。

class BannedBook {
	public:
	vector<string> F;
	vector<int> R;
	int vis[51];
	
	void dfs(int cur,int d) {
		if(vis[cur]) return;
		vis[cur]=1;
		if(d==0) R.push_back(cur);
		int i;
		FOR(i,F.size()) if(F[cur][i]=='Y' && vis[i]==0) dfs(i,d^1);
		if(d) R.push_back(cur);
	}
	
	vector <int> passAround(vector <string> F) {
		this->F=F;
		ZERO(vis);
		R.clear();
		int i;
		FOR(i,F.size()) if(vis[i]==0) dfs(i,0);
		return R;
		
	}
}

まとめ

この場合距離２以下の移動だけでも十分？