kmjp's blog

競技プログラミング参加記です

TopCoder SRM 733 Div2 Hard HamiltonianPathsInGraph

ずいぶんシンプルに書けるのね。
https://community.topcoder.com/stat?c=problem_statement&pm=14881

問題

N要素のトーナメントグラフが与えられる。
ここからN頂点のハミルトンパスを構築せよ。

解法

Div2で1位の人のコードがとてもわかりやすい。
https://community.topcoder.com/stat?c=problem_solution&rm=331165&rd=17140&pm=14881&cr=40741634

頂点集合Vに対し、Vの要素を1つずつ用いるパスの1例をPath(V)とする。
Vからなる元のグラフの部分グラフに対し、Path(V)は最低1個は存在することを用いて再帰的に構築する。

  • Path(φ)は空の数列である。
  • Path(V)について、先頭要素をuとするとき、Vに含まれるu以外の頂点vは以下のようにBefore(V)かAfter(V)に分類される。
    • Before(V) := v→uの向きの辺があるようなvの集合
    • After(V) := u→vの向きの辺があるようなvの集合

この時Path(V) = Path(Before(V)) + [u] + Path(After(V))となる。
Before(V)の中の頂点はいずれもuに向けて辺をもつので、Path(Before(V))の末尾の頂点が何であっても、次にvをつなげられる。
After(V)も同様。

class HamiltonianPathsInGraph {
	public:
	int N;
	vector<string> S;
	
	vector<int> hoge(vector<int> V) {
		if(V.empty()) return V;
		vector<int> A,B;
		for(int i=1;i<V.size();i++) {
			if(S[V[0]][V[i]]=='+') A.push_back(V[i]);
			else B.push_back(V[i]);
		}
		A=hoge(A);
		B=hoge(B);
		B.push_back(V[0]);
		FORR(v,A) B.push_back(v);
		return B;
	}
	
	vector <int> findPath(vector <string> X) {
		S=X;
		N=S.size();
		
		vector<int> V;
		int i;
		FOR(i,N) V.push_back(i);
		return hoge(V);
	}
}

まとめ

この手順だと、必ずハミルトンパスが存在することが示せるね。