Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no repeated vertices or edges.
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 the number of cycles in the given graph.
4 61 21 31 42 32 43 4
7
The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.
题意:
求一个图中(节点个数小于20)长度大于等于三的哈密顿路径数目。
思路:
点数不多,类似TSP,用状压dp解决。
dp[i][j]表示状态为i时。以j结尾的路径条数。
假设下一个点能回到已经走过的一个点中,那么就是一个回路了。
为了避免反复计算,回到的点为走过的最小的点。(这是一个优化,少了枚举最小点这个循环)
长度为2的哈密顿路径会计算到,能够不做处理,最后减去边的条数就可以,每一个环会算两遍,最后要除以2.
代码:
#include#include #include #include #include #include #include