Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no repeated vertices or edges.
Input
The first line of input contains two integers n and m (1 ≤ n ≤ 19, 0 ≤ m) – respectively the number of vertices and edges of the graph. Each of the subsequent m lines contains two integers a and b, (1 ≤ a, b ≤ n, a ≠ b) indicating that vertices a and b are connected by an undirected edge. There is no more than one edge connecting any pair of vertices.
Output
Output the number of cycles in the given graph.
Examples
input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
output
7
Note
The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.
分析:求簡單環個數,n很小,但是爆搜是不行的。。因為結果是階乘級别的,考慮狀壓dp,f[i][s][t]表示目前鍊中點的集合為i,起點為s終點為t的所有方案數,因為s,t必定屬于i,而且一個簡單環有多重表示方法,是以我們考慮精簡狀态,f[i][t]表示起點s 為 i 中編号最小點,終點為t的所有鍊方案數,最後如果edg(s,t)存在就将f[i][t]記入答案,因為環上每點有兩個相鄰點,是以最後答案要除以二。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
#define INF 2147483640
#define eps 1e-9
#define MAXN 0x3f
#define N 20
using namespace std;
int n,m,u,v,fh[1<<19];
unsigned long long ans,dp[1<<19][N];
bool edg[N][N];
int f(int x)
{
return 1<<(x-1);
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++) fh[f(i)] = i;
for(int i = 1;i <= m;i++)
{
cin>>u>>v;
edg[u][v] = edg[v][u] = true;
}
for(int i = 1;i <= (1<<n)-1;i++)
for(int t = fh[i & (-i)] + 1;t <= n;t++)
if(f(t) & i)
{
int s = fh[i & (-i)],sta = i - f(t) - f(s);
if(!sta)
{
dp[i][t] = edg[s][t];
continue;
}
for(int j = sta;j;j -= j & (-j))
if(edg[fh[j & (-j)]][t])
dp[i][t] += dp[i - f(t)][fh[j & (-j)]];
if(edg[s][t]) ans += dp[i][t];
}
cout<<ans/2<<endl;
}