TopCoder SRM 531 Div1 Medium MonsterFarm

問題

1〜n番までのn種類のモンスターがいる。
最初は1番のモンスターが1匹いる。

一日たつと、i番目のモンスターは、それぞれ与えられたモンスター（一匹以上）へと変化する。
最終的にモンスターは何匹になるか、
モンスターが無限に増える場合は-1を、そうでないならその数をmod 10^9 + 7で求めよ。

制約条件

n≦50

方針

モンスターの変化の関係をグラフにする。
すなわち、i番目のモンスターからj番目のモンスターが1匹生まれるとき、
iからjへ重さ1の辺を張る。

モンスターが無限に増えるのは、このグラフを強連結成分分解したときに、
（最初のモンスターから到達可能な）一つの連結成分のなかに、
出次数2以上の頂点があることと同値。

ただしセルフループがある場合がちょっとコーナーケースになっているので別途処理する。

上の条件を満たす場合-1を出力し、そうでないときは100ターンしないうちにモンスターの数は変化しなくなるので、
100ターンシミュレーションしてその数を出力すればいい。

ソースコード

const int mod=(int)1e9+7;
int n, e[50][50];
int out[50], nk, cmp[50];
bool can[50][50];

struct MonsterFarm{
	int numMonsters(vector<string> transforms){
		n=transforms.size();
		for(int i=0;i<n;i++){
			stringstream ss(transforms[i]);
			int t;
			while(ss>>t)e[i][--t]++, out[i]++;
		}
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)can[i][j]=e[i][j];
		for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)can[i][j]|=can[i][k]&&can[k][j];
		
		for(int i=0;i<n;i++)if(can[0][i]&&e[i][i]>=1&&e[i][i]+out[i]>2)return -1;
		
		nk=0;
		for(int i=0;i<n;i++)cmp[i]=-1;
		for(int i=0;i<n;i++)if(cmp[i]<0){
			for(int j=i+1;j<n;j++)if(can[i][j]&&can[j][i])cmp[j]=nk;
			cmp[i]=nk++;
		}
		for(int i=0;i<nk;i++){
			int cnt=0;
			for(int j=0;j<n;j++)if(cmp[j]==i&&can[0][j])cnt++;
			for(int j=0;j<n;j++)if(cmp[j]==i&&cnt>1&&out[j]>1)return -1;
		}
		
		vector<int> cnt(n);
		cnt[0]=1;
		for(int i=0;i<100;i++){
			vector<int> nxt(n);
			for(int j=0;j<n;j++)for(int k=0;k<n;k++)(nxt[k]+=(long long)cnt[j]*e[j][k]%mod)%=mod;
			cnt=nxt;
		} 
		int ans=0;
		for(int i=0;i<n;i++)(ans+=cnt[i])%=mod;
		return ans;
	}
};