AtCoder Beginner Contest 041D

D - 徒競走

トポロジカルソートの場合の数を数え上げる問題．
これはDPで可能．

を頂点集合の部分集合とする．
をトポロジカルソートする場合の数，
を，の元のうち，出次数が0の頂点全体
とする．
の元 に関して場合分けして数え上げる．
を一番端にもってくる場合の数はとなる．

よって，

という遷移で求まる．

typedef long long ll;

using vll = vector<long long>;  using vvll = vector<vll>;

#define srep(i,s,t) for (ll i = (s); i < (t); ++i)

#define rep(i,n) srep(i,0,(n))

int main() {

    ll n,m; cin >> n >> m;

    vvll to(n);

    rep(i,m){

        ll a, b; cin >> a >> b;

        --a, --b;

        to[a].push_back(b);

        //to[b].push_back(a);

    }

   

    vll dp(1LL<<n);

    dp[0] = 1;

    rep(s,1LL<<n) if(s){

        rep(i,n) if(s>>i&1){

            bool f = true;

            fore(x, to[i]){

                if(s>>x&1) f = false;

            }

            if(f) {

                ll t = s ^ (1LL<<i);

                dp[s] += dp[t];

            }

        }

    }

    cout << dp[(1LL<<n)-1] << endl;

    return 0;

}