TopCoder SRM 685 Div1 Easy MultiplicationTable2

Resubmit等グダグダだったけど、Mediumがそこそこの時間で解けたのでレート増。
https://community.topcoder.com/stat?c=problem_statement&pm=14194

問題

0～(N-1)のN個の整数からなる集合Sの内部で成り立つ二項演算子＄がある。
入力として、この二項演算子の結果を示すN*N要素の行列が与えられる。

Sの部分集合S'で、S'内の2要素に＄を適用しても結果がS'に収まるようなもののうち、最小サイズを求めよ。

解法

S'の初期要素として、0～(N-1)のうち単一要素で構成されるものを考える。
x,y∈S'に対し(x$y)をS'に追加するという処理を、S'が増加しなくなるまで繰り返してサイズを見ればよい。

int T[51][51];

class MultiplicationTable2 {
	public:
	int minimalGoodSet(vector <int> table) {
		int N=1;
		int y,x,i;
		while((N+1)*(N+1) <= table.size()) N++;
		FOR(y,N) FOR(x,N) T[y][x]=table[y*N+x];
		
		int mi=N;
		FOR(x,N) {
			int in[50]={};
			vector<int> V,V2;
			V2.push_back(x);
			in[x]=1;
			
			while(V2.size()) {
				FORR(r,V2) V.push_back(r);
				V2.clear();
				int x2,y2;
				FORR(r,V) FORR(r2,V) {
					int z=T[r][r2];
					if(in[z]==0) {
						V2.push_back(z);
						in[z]=1;
					}
				}
			}
			mi=min(mi,(int)V.size());
		}
		return mi;
	}
}

まとめ

最初O(N^5)の解を書いてResubmitしてO(N^4)にしたけど、O(N^5)でも通ったかな…？