ずいぶんシンプルに書けるのね。
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); } }
まとめ
この手順だと、必ずハミルトンパスが存在することが示せるね。