ABC 041-D 徒競走

ABC041D.cpp

#include<iostream>
 
using namespace std;
#define int long long
 
int N, M;
int memo[1<<16];
int g[16][16];
 
int rec(int S){
 
   if(memo[S]!=0) return memo[S];
   if(S==0){
      return 1;
   }
   int ret=0;
   for(int j=0; j<N; j++){
      if(!((S>>j)&1)) continue;
      for(int k=0; k<N; k++){
         if((S>>k)&1 && g[j][k]){
            goto failed;
         }
      }
      ret+=rec(S-(1<<j));
      failed:;
   }
   return memo[S]=ret;
}
 
signed main(){
 
   cin>> N>> M;
   for(int i=0; i<M; i++){
      int a, b;
      cin>> a>> b;
      g[a-1][b-1]=1;
   }
 
   cout<< rec((1<<N)-1)<< endl;
 
   return 0;
}