fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h> 
  3. typedef long long ll; 
  4.  
  5. using namespace std;
  6. int n; 
  7. vector<vector<int>>adj; 
  8. ll dp[20][(1<<19)]; 
  9.  
  10. ll solve(int i, int mask){
  11.  
  12.   if(~dp[i][mask]) return dp[i][mask]; 
  13.  
  14.   ll ans = 0ll; 
  15.  
  16.   for(auto x: adj[i]){
  17.      if((mask&(1<<x)) != 0) ans++; 
  18.      else ans += solve(x,mask|(1<<x)); 
  19.   } 
  20.   return dp[i][mask] = ans; 
  21.  
  22. }
  23. int main() {
  24. 	ios_base::sync_with_stdio(false); 
  25.     cin.tie(NULL); cout.tie(NULL); 
  26.  
  27.     memset(dp,-1,sizeof(dp)); 
  28.     cin>>n; int m; cin>>m; 
  29.     adj.resize(n); 
  30.     ll ans = 0; 
  31.     for(int i = 0; i < m; i++){
  32.        int u,v; cin>>u>>v; u--; v--; 
  33.        adj[u].push_back(v); 
  34.        adj[v].push_back(u); 
  35.  
  36.     }
  37.     for(int i = 0; i < n ; i++){
  38.         bool ok = 1; 
  39.         for(int mask = 0; mask < (1<<n) ; mask++){
  40.             if(~dp[i][mask]) {ok = 0; break;} 
  41.  
  42.          }
  43.          if(ok) ans += solve(i,0); 
  44.  
  45.     }
  46.     cout<<ans - m<<endl; 
  47.  
  48. }
  49.  
Success #stdin #stdout 0.01s 85492KB
comments (?)
stdin
copy 
4 6
1 2
1 3
1 4
2 3
2 4
3 4
stdout
copy 
93
https://ideone.com/5qkLe3
language:
C++ (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!