首页 > 题解 > codeforce 11D A Simple Task

codeforce 11D A Simple Task


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.

题意

求一个图长度大于等于三的哈密顿路径数目。

题解

状压,f[i][j]表示状态为i时,以j结尾的路径条数。

如果下一个点能回到已经走过的一个点中,那么就是一个回路了。

为了避免重复计算,回到的点为走过的最小的点。(这是一个优化,少了枚举最小点这个循环)

长度为2的哈密顿路径会计算到,可以不做处理,最后减去边的条数即可,每个环会算两遍,最后要除以2.


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×