Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.0 kB
2
Indexable
Never
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
const int mod = 1e9+7;
int dp[1 << 22][22];
bool mark[22][22];
using namespace std;

int main(){
    ios;
    int a , b  , u , v;
    cin >> a >> b;
    for(int i = 0 ; i < b ; i++){
        cin >> u >> v;
        u--;v--;
        mark[u][v] = true;
        dp[1 << u][u] = 1;
        dp[1 << v][v] = 1;
    }
    int cnt = 0;
    for(int mask = 1 ; mask < (1 << a)-1 ; mask++){
        for(int i = 0 ; i < a ; i++){
            if(((mask >> i) & 1) && (mask != (1 << i)) && cnt+1 != (__builtin_popcount(mask))){
                cnt++;
                for(int j = 0 ; j < a ; j++){
                    if(((mask >> j) & 1) && mark[1 << i][j] && j != i){
                        (dp[mask][i] += dp[mask ^ (1 << i)][j]) %= mod;
                    //    cout << dp[mask][i] << ' ';
                    }
                }
            }
        }
    }
    cout << dp[(1 << a)-1][0]; 
    return 0;
}