コード
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++;
}
}
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;
}
}