トポロジカルソート（HashMapでメモ化再帰）

ABC041_D

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.math.*;

public class Main {
	static HashMap<String, Long> map = new HashMap<String, Long>();

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] str = br.readLine().split(" ");
		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);

		int[] f = new int[m];
		int[] b = new int[m];
		for(int i = 0; i < m; i++){
			String[] s = br.readLine().split(" ");
			f[i] = Integer.parseInt(s[0]) - 1;
			b[i] = Integer.parseInt(s[1]) - 1;
		}

		BitSet bs = new BitSet(n);
		bs.flip(0,n);

		long sum = solve(bs,f,b,n,m);
		sb.append(sum);
		System.out.println(sb);
	}
	
	public static long solve(BitSet bs, final int[] f, final int[] b, final int n, final int m){
		long sum = 0;

		//memo check
		String s = bs.toString();
		if(map.containsKey(s))
			return map.get(s);

		BitSet available = new BitSet(n);
		for(int i = 0; i < m; i++){
			if(bs.get(f[i]))
				available.set(b[i]);
		}
		available.flip(0,n);
		available.and(bs);

		for(int i = available.nextSetBit(0); i >= 0; i = available.nextSetBit(i+1)){
			BitSet tmp = (BitSet)bs.clone();
			tmp.flip(i,i+1);
			sum += solve(tmp,f,b,n,m);
		}
		if(sum == 0)sum++;

		//memo
		map.put(bs.toString(), sum);

		return sum;
	}
}