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 mlines contains two integers a and b, (1 ≤ a, b ≤ n, a ≠ b) indicating that vertices aand 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.
Example
4 6
1 2
1 3
1 4
2 3
2 4
3 4
7
Note
The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.
1-2-3 2-3-4 1-3-4 1-2-4 1-2-3-4 1-2-4-3 1-4-2-3
题意:给出一个图的点数和边数输出这个图中有几个环.
题解:这道题可以很容易想到状压,因为数据也只有19(orz).用sta的二进制表示已经有几个点在这个状态中,那怎么表示形成环呢?只需要找到一个当前状态中的点,它神奇的与前面的某一个点有一条边连着,那么说明肯定能构成环,可以为总答案做贡献.如果不能,那么就为下一个状态提供个数.不过由于是无向图.所以两个点也会被认为成环(两个点构成环的个数为边数),并且每个更大的环都会被计算两次,所以最后要减掉.然后就搞定了.
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std; long long dp[<<][],ans=;
vector<int> e[]; int lowbit(int x)
{
return x&(-x);
} int main()
{
int n,m,f,t;
scanf("%d%d",&n,&m); for(int i=;i<m;i++)
{
scanf("%d%d",&f,&t);
e[f-].push_back(t-);
e[t-].push_back(f-);
} for(int i=;i<n;i++)
{
dp[<<i][i]=;
} for(int sta=;sta<(<<n);sta++)
{
for(int i=;i<n;i++)
{
if(dp[sta][i])
{
for(int k=;k<e[i].size();k++)
{
int j=e[i][k];
if(lowbit(sta)>(<<j))
{
continue;
}
if(sta&(<<j))
{
if(lowbit(sta)==(<<j))
{
ans+=dp[sta][i];
}
}
else
{
dp[sta|(<<j)][j]+=dp[sta][i];
}
}
}
} ans=(ans-m)/;
printf("%lld\n",ans);
return ;
}
每天刷题,身体棒棒!