Codeforces 11 D. A Simple Task

問題

n個の頂点およびm本の辺からなる無向グラフが与えられる。
このグラフに含まれる閉路の個数を求めよ。

制約条件

n≦19

方針

まずは頂点0を含む閉路を考える。
これはdp[pos][mask]を、現在posにいて、今までmaskで表される集合の点を訪問する場合の数とする。
これをループをまわして、
頂点0から頂点0へ移動する経路の数を数える。


次に、グラフから頂点0を削除し、
頂点1を含む閉路をDPでと同様に数えて足す。
頂点1を削除して……と同様に繰り返す。


右回りと左回りで同じ閉路が二回数えられているので最後に2で割る。

ソースコード

int n,m;
bool e[20][20];
ll dp[20][1<<20],ans;


void run(){
  cin>>n>>m;
  memset(e,0,sizeof(e));
  rep(i,m){
    int a,b; cin>>a>>b;
    a--; b--;
    e[a][b]=e[b][a]=1;
  }
  ans=0;
  for(int s=n-1;s>1;s--){
    rep(i,s+1)rep(j,1<<s+1)dp[i][j]=0;
    dp[s][0]=1;
    
    rep(mask,1<<s+1)rep(i,s+1)rep(j,s+1)if(e[i][j]&&!(mask&1<<j)){
      dp[j][mask|1<<j]+=dp[i][mask];
    }
    rep(i,1<<s+1)if(__builtin_popcount(i)>2)ans+=dp[s][i];
  }
  cout<<ans/2<<endl;
}