题目名称	996. [NOIP 2010冲刺四]晨跑路径
输入输出	`running.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	sywgz 于2012-08-07加入
开放分组	全部用户
提交状态
分类标签	搜索法图论
	分享题解

通过：17，提交：68，通过率：25%
zxj	100	0.006 s	3.75 MiB	C++
Lethur	100	0.008 s	0.35 MiB	C++
Hexฏ๎๎๎๎๎๎๎๎๎ۣۣۣ	100	0.010 s	0.33 MiB	C++
KZNS	100	0.011 s	0.35 MiB	C++
Rapiz	100	0.014 s	0.34 MiB	C++
sxysxy	100	0.019 s	0.35 MiB	C++
Makazeu	100	0.028 s	0.38 MiB	C++
codewaysky	100	0.029 s	0.36 MiB	C++
Truth.Cirno	100	0.053 s	3.30 MiB	C++
lingyixiaoyao	100	0.090 s	0.46 MiB	C++

本题关联比赛
20120808

关于晨跑路径的近10条评论(全部评论)
回复 @KZNS : %%%% Rapiz 2016-10-27 16:17 10楼
tarjan求割点，从1开始，要求子树中存在点N才算是合格的割点 KZNS 2016-10-13 08:22 9楼
数据有问题吧..... 旺仔小馒头 2016-05-28 21:03 8楼
第一组测试数据是这样的 4 2 100 20 100 70 1 测试数据有没有问题啊这就不是一道题啊残镖书生 2015-03-04 11:38 7楼
回复 @HouJikan : +1？ hjf222289 2015-02-26 18:56 6楼
输入数据有问题？ HouJikan 2014-09-14 22:33 5楼
Tarjan了。。 Makazeu 2012-11-02 23:04 4楼
错误1：需求：n变量全局定义；结果：n变量全局局部都有定义。导致：跪错误2：tarjan求出的割点可能会出现同一个点多次被求出的情况，需判断。以后需注意：“根”节点的情况单独判断，当从其发出的“儿子”大于1时，则该点为割点，否则不为割点。 Truth.Cirno 2012-11-02 19:00 3楼
在学到效率最高的算法前，打死不用o（n^2）天下第一的吃货殿下 2012-10-31 21:33 2楼
先求割点，然后枚举 codewaysky 2012-10-23 16:03 1楼

996. [NOIP 2010冲刺四]晨跑路径

★ 输入文件：running.in 输出文件：running.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

新牛到部队，CG要求他们每天早上晨跑，从A农场跑到B农场。从A农场到B农场中有n-2个路口，分别标上号A农场为1号，B农场为n号，路口分别为2..n-1号，从A农场到B农场有很多条路径可以到达，而CG发现有的路口时必须经过的，即每一条路径都经过的路口，CG要把他们记录下来，这样CG就可以先到达那个路口，观察新牛们有没有偷懒，而你的任务就是找所有必经路口。

【输入数据】

第一行两个用空格隔开的整数n（3<=n<=2000)和e(1<=e<=8000)。

接下来从第2行到第e+1行，每行两个用空格隔开的整数p和q，表示路口p和q之间连通。

输入数据保证必经路口一定存在，并且每个路口都和A农场，B农场相连通。

【输出数据】

第一行一个整数m，表示必经路口的数目。

第二行按从大到小的顺序依次输出每个必经路口的编号，每两个数之间用空格隔开。

注意：不包括起点和终点

【样例输入】

6 6
1 2
2 4
2 3
3 5
4 5
5 6

【样例输出】

2
2 5