Submission #2709635

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
typedef long long ll;

const int MAX_N=16;

int N,M;

vector<int> G[MAX_N];

ll memo[1<<MAX_N];

ll dfs(int bit){
	if (bit==(1<<N)-1){
		return 1;
	}
	if (memo[bit]!=-1){
		return memo[bit];
	}
	ll res=0;
	REP(i,N){
		if (!((bit>>i)&1)){
			bool flg=true;
			REP(j,(int)G[i].size()){
				if (!((bit>>G[i][j])&1)){
					flg=false;
				}
			}
			if (flg){
				res+=dfs(bit+(1<<i));
			}
		}
	}
	return memo[bit]=res;
}

int main(){
	cin>>N>>M;
	REP(i,M){
		int x,y;
		cin>>x>>y;
		x--;
		y--;
		G[y].push_back(x);
	}
	memset(memo,-1,sizeof(memo));
	cout<<dfs(0)<<endl;
	return 0;
}

Submission Info

Judge Result