読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 531 Div1 Medium: MonsterFarm

コード

import java.util.Arrays;

public class MonsterFarm {
	private final int MOD = (int) 1e9 + 7;

	public int numMonsters(String[] transforms) {
		int N = transforms.length;

		int[][] edge = new int[N][N];
		int[] out = new int[N];
		for (int i = 0; i < N; i++) {
			String[] kinds = transforms[i].split(" ");
			for (int j = 0; j < kinds.length; j++) {
				int k = Integer.parseInt(kinds[j]) - 1;
				edge[i][k]++;
				out[i]++;
			}
		}

		// ワーシャルフロイト
		boolean[][] map = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = edge[i][j] > 0;
			}
		}
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = map[i][j] || (map[i][k] && map[k][j]);
				}
			}
		}

		// セルフループで無限に増える時
		for (int i = 0; i < N; i++) {
			if (map[0][i] && edge[i][i] >= 1 && edge[i][i] + out[i] > 2) {
				return -1;
			}
		}

		// 強連結成分分解
		int group = 0;
		int[] cmp = new int[N];
		Arrays.fill(cmp, -1);
		for (int i = 0; i < N; i++) {
			if (cmp[i] < 0) {
				for (int j = i + 1; j < N; j++) {
					if (map[i][j] && map[j][i]) {
						cmp[j] = group;
					}
				}
				cmp[i] = group;
				group++;
			}
		}

		for (int g = 0; g < group; g++) {
			int cnt = 0;// 強連結成分内の要素数
			for (int j = 0; j < N; j++) {
				if (cmp[j] == g && map[0][j]) {
					cnt++;
				}
			}

			// ループしているのにoutが2以上だと永久機関になる
			for (int j = 0; j < N; j++) {
				if (cmp[j] == g && cnt > 1 && out[j] > 1) {
					return -1;
				}
			}
		}

		// シミュレーション
		long[] cnt = new long[N];
		cnt[0] = 1;
		for (int turn = 0; turn < 1000; turn++) {
			long[] next = new long[N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					next[j] += ((long) cnt[i] * edge[i][j]) % MOD;
					next[j] %= MOD;
				}
			}
			cnt = next;
		}

		long ans = 0;
		for (int i = 0; i < N; i++) {
			ans += cnt[i];
			ans %= MOD;
		}
		return (int) ans;

	}
}