SRM 405: AllCycleLengths

(問題概要)
有向グラフが与えられる(ノード数<=30)。
好きなところからスタートしてi回(i = 1, 2, ...)の移動後最初の地点に戻れるか。
各iに対して戻れるなら1戻れないなら0を並べたものを計算せよ。
ただし結果は以下の一番短くなるフォーマットで
010(110) (意味: 010110110110110... (010の後に110がループ)

(解法)
分からんので解説読んだ。
解説「ループの長さはそんなに長くないので、全通り試せ」
なんとなくループの長さ長くないとは思ってたけど、証明わからないからその発想には至らなかった…

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class AllCycleLengths {
public:
  string findAll(vector <string> arcs);
};

inline bool cango(vector<string> &arcs, int from, int to){
  return arcs[from][to] == 'Y';
}

string AllCycleLengths::findAll(vector <string> arcs){
  const int n    = arcs.size();
  const int MAX  = 1000;
  const int LMAX = 50;

  vector<int> ans(MAX);

  REP(i,n){
    vector<int> flag(n);
    flag[i] = 1;
    REP(j,MAX + 1){
      vector<int> next(n);

      if(j != 0 && flag[i])
	ans[j - 1] = 1;

      REP(k,n) if(flag[k]){
	REP(l,n) if(cango(arcs, k, l)){
	  next[l] = 1;
	}
      }

      flag.swap(next);
    }
  }

  stringstream ss;

  REP(i,MAX){
    for(int len = 1; len <= LMAX; len++){
      bool ok = true;
      for(int p = 0; i + p < MAX; p++)
	if(ans[i + p] != ans[i + (p % len)])
	  ok = false;

      if(ok){
	REP(j,i) ss << ans[j];
	ss << '(';
	REP(j,len) ss << ans[i + j];
	ss << ')';
	goto end;
      }
    }
  }

  end:
  return ss.str();
}