2010年 夏合宿4日目 Problem A : Alien's Counting [Licence: NYSL Version 0.9982]

Alien.java

import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Alien {
  public static void main(String... args) throws Exception {
		new Alien().run();
	}

	static final int MOD = 1000000007;

	public void run() throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] S = new int[N];
		fill(S, -1);
		for(int i = 0; i < M; i++)
			S[Integer.parseInt(sc.next()) - 1] = Integer.parseInt(sc.next()) - 1;

		// topological sort
		int[] tp = new int[N];
		boolean[] used = new boolean[N];
		for(int i = 0, c = N - 1; i < N; i++)
			if(!used[i]) {
				Deque<Integer> st = new ArrayDeque<Integer>();
				for(int j = i; j >= 0 && !used[j]; j = S[j]) {
					st.offerFirst(j);
					used[j] = true;
				}
				while(!st.isEmpty())
					tp[c--] = st.pollFirst();
			}

		// loop detection
		int[] g = new int[N];
		used = new boolean[N];
		for(int p : tp) {
			used[p] = true;
			if(S[p] >= 0 && used[S[p]]) {
				for(int q = S[p]; q != p; q = S[q])
					g[q] = S[p];
				g[p] = S[p];
			}
			else
				g[p] = p;
		}

		// contraction
		int[] T = new int[N];
		fill(T, -2);
		for(int i = 0; i < N; i++)
			if(g[i] == i)
				T[i] = (S[i] < 0 || g[S[i]] == g[i] ? -1 : g[S[i]]);

		// dp
		long ans = 1;
		long[] dp = new long[N];
		fill(dp, 1);
		for(int i : tp)
			if(T[i] > -2) {
				dp[i] = (dp[i] + 1) % MOD;
				if(T[i] == -1)
					ans = (ans * dp[i]) % MOD;
				else
					dp[T[i]] = (dp[T[i]] * dp[i]) % MOD;
			}

		System.out.println(ans);
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}