原题大意

统计一个无向图中环的个数

算法分析

首先考虑到一个环其实是一条链两头连接起来的，所以我们只要找到所有的链判一下两头是否联通即可。但是一个链的状态是首尾和经过的点，是n^2*2^n的，考虑到题目限制n<=19，这个状态数显然是爆炸的。现在我们考虑人为地把一个环从经过的点中id最小的点的两侧处切开，则得到了两个以id最小值为起点的链。对于任意的环我们都可以这样做，于是我们只要统计以id最小值为起点的成环链的数量，将结果除以2即可。这样由于起点已经固定，状态数就只有n*2^n, 然后dp一下即可。
dp[i][j]表示状态i（具体路径）中，以i的最小id为起点，j为终点的路径数。

http://m.blog.csdn.net/article/details?id=49078233
http://blog.csdn.net/kk303/article/details/9621933

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool g[20][20];
ll dp[1<<20][20];
int n, m;
int main()
{
    cin>>n>>m;
    memset(g, false, sizeof(g));
    while(m--){
        int a, b;
        cin>>a>>b;
        g[a-1][b-1]=g[b-1][a-1]=true;
    }
    ll ans=0;
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)dp[1<<i][i]=1;
    for(int i=0;i<1<<n;i++){
        for(int j=0;j<n;j++){
            if(dp[i][j] == 0)continue;
            int st=0;
            for(int k=0;k<n;k++){
                if(i&(1<<k)){
                    st=k;
                    break;
                }
            }
            //__builtin_popcount()是计算一个数字二进制里有多少1
            if(g[st][j]&&__builtin_popcount(i)>2)ans+=dp[i][j];
            for(int k=st+1;k<n;k++){
                if(!(i&(1<<k))&&g[j][k])dp[i|(1<<k)][k]+=dp[i][j];
            }
        }
    }
    cout<<ans/2<<endl;
}