简单环

[编程题]简单环

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一张n个点m条边的无向图，求出图中所有简单环的数量。(简单环：简单环又称简单回路，图的顶点序列中，除了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路叫简单回路。或者说，若通路或回路不重复地包含相同的边，则它是简单的)

输入描述:

第一行三个数n m k (k在输出描述中提到)
接下来m行每行两个数u，v表示u到v之间存在一条边（无重边）

输出描述:

输出k行每行1个整数
第i个数表示长度%k==i-1的简单环的数量（对998244353取模）
(只记录长度大于2的简单环的数量)

示例1

输入

输出

4
3
0

备注:

n<=20
m<=n*(n-1)/2
k<=n

算法知识视频讲解

瑜画

发表于 2020-08-17 14:55:12

前面部分跟“郊区春游”差不多，属于TSP问题，不懂的可以看一下我郊区春游的那篇题解。也是枚举起点、终点（终点这里得比起点大，避免重复统计），进行状态转移，不同的是这里的dp数组记录的是方案数量，然后每次转移以后要判终点和起点是否可以相连，相连就进行统计。最后答案要除以2，原因是大于等于3的回路可能会展开全文

在刷题的单身狗很开心

发表于 2023-10-26 01:05:27

//动态规划数组依旧是：dp[state][j];i表示状态，j表示在当前状态下的结尾节点。 //但不同的在于这道题要找简单环，而对于找简单环来说定起点和终点是比较重要的。 //因为只有知道了起点和终点，然后又知道起点和终点是否有一条直接的线连接，就证明是不是环。 //如果我们单纯的去执行状态转移方展开全文