2 shunfurh shunfurh 于 2017.09.14 11:00 提问

Cactus

Cactus is a connected undirected graph in which every edge lies on at most one simple cycle. Intuitively cactus is a generalization of a tree where some cycles are allowed. Your task first is to verify if the given graph is a cactus or not. Important difference between a cactus and a tree is that a cactus can have a number of spanning subgraphs that are also cactuses. The number of such subgraphs (including the graph itself) determines cactusness of a graph (this number is one for a cactus that is just a tree). The cactusness of a graph that is not a cactus is considered to be zero.

The first graph on the picture is a cactus with cactusness 35. The second graph is not a cactus because edge (2, 3) lies on two cycles. The third graph is not a cactus because it is not connected.

Input

The first line of each test case contains two integer numbers n and m (1 ≤ n ≤ 20000, 0 ≤ m ≤ 1000).

Here n is the number of vertices in the graph. Vertices are numbered from 1 to n. Edges of the graphare represented by a set of edge-distinct paths, where m is the number of such paths.

Each of the following m lines contains a path in the graph. A path starts with an integer number ki(2 ≤ ki ≤ 1000) followed by ki integers from 1 to n. These ki integers represent vertices of a path. Path can go to the same vertex multiple times, but every edge is traversed exactly once in the whole input file.

There are no multiedges in the graph (there is at most one edge between any two vertices).

The whole input consists of several test cases. Proceed to the end of file.

Output

For each test case, write to the output file a single integer number - the cactusness of the given graph. Note that cactusness can be quite a large number.

Sample Input

14 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
2 2 14
10 2
7 1 2 3 4 5 6 1
6 3 7 8 9 10 2
5 1
4 1 2 3 4
Sample Output

35
0
0

1个回答

devmiao
devmiao   Ds   Rxr 2017.09.30 08:32
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
[仙人掌同构 Hash] Codeforces Gym 100307 NEERC 13 C. Cactus Automorphisms
其实就是BZOJ3899的加强版 当时写的东西真是不敢恭维还是看Po姐的题解吧 我们把仙人掌拆成圆方树 就可以直接用树hash来做 先找重心 因为我写的时候把两个点也当做点双 那么所有边都是圆方相接如果重心有两个 去代表环的方点就好了 接下来是hash 圆点没问题 子树排完序hash 顺带记一下如果有相同 答案乘上出现次数的阶乘 不是根的方点 也就是一个环 是有顺序的 不能排序 然后看一
使用cactus进行单元测试的方法
 一、在web.xml中配置返调servlet    servlet>        servlet-name>ServletRedirectorservlet-name>        servlet-class>            org.apache.cactus.server.ServletTestRedirector        servlet-class>    serv
一个cactus测试的例子,用eclipse
以前apache提供cactus的eclipse插件,但是因为cactus是基于juint的,所以现在没有插件了。另外apache上面的文档关于如何集成到eclipse的部分还没有换。http://jakarta.apache.org/cactus/integration/eclipse/runner_plugin.html和http://jakarta.apache.org/cactus/int
Java单元测试Junit(四)使用Cactus测试Servlet
什么是Cactus?        Cactus是Apache下的一个开源测试Web层的框架,可以完成模拟J2EE的容器来进行测试,可以测试Servlet,JSP,Filter,EJB等等,以下图片为Cactus官方网站的原理图                                        当测试DAO时我们可以使用DBUnit来进行对数据库的隔离,当我们测试Service的
Cactus入门
完整版见https://jadyer.github.io/2013/07/11/cactus-servlet/
easymock,cactus测试controller
一、变量等的初始化操作 @Before//每一个测试单元都会执行 @BeforeClass//只会执行一次,方法必须为静态方法二、使用easymock测试 maven添加easymock依赖: <dependency> <groupId>org.easymock</groupId> <artifactId>easymock</artifactId>
听说你会图论
=============================以下是最小生成树+并查集====================================== 【HDU】 1213 How Many Tables 基础并查集★ 1272 小希的迷宫 基础并查集★ 1325&&poj1308 Is It A Tree? 基础并查集★ 1856 More is better
cactus在Junit测试时需要添加的内容
根据apache的start文档做了一个例子,但是发现在Run As Junit时一直出错 Missing Cactus property [cactus.contextURL]后来发现少了一个文件cactus.properties,内容如下:cactus.contextURL=http://localhost:8080/Cactuscactus.servletRedirectorName
HDU - 3594 Cactus(仙人掌图)
题目大意:给出仙人掌图的定义: 1.必须是强连通 2.每条边只能属于一个环解题思路:在tarjan算法中加入点东西就可以判断了 只要该点能连到之前的点,那么形成环了,找到这个环的所有的边,并标记 如果有一条边被标记了两次了,那图就不是仙人掌图了关键是怎么找到这个环的所有边,我们可以引入另一个栈,这个栈存放的是边的序号 假设当前点为u,u点连回之前的点是v,那么就从栈里面找边,找到出发点为v
[SHOI2008]cactus仙人掌图 (tarjan + dp)
Description 如果某个无向连通图的任意一条边至多只出现在一条简单回路(simple cycle)里,我们就称这张图为仙人图(cactus)。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。 举例来说,上面的第一个例子是一张仙人图,而第二个不是——注意到它有三条简单回路:(4,3,2,1,6,5,4)、(7,8,9,10,2,3,7)以及(4,3,7,8,9,10,2,1,6,5,