当前位置:首页 > 图论 > 图的遍历 > 正文
洛谷P1793跑步[NOI导刊]
682+

题目大意:n个点,m条边,从起点1到终点n的路径中,哪些点是必须经过的?

题目描述

新牛到部队, 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,表示必经路口的数目。

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

输入输出样例

输入样例 #1

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

输出样例 #1

2
2 5

解题思路

割点即必经之点,但数据范围比较小,可以暴力。

暴力枚举必经之点2~n-1,将这个点的边全部“删掉”,跑一遍Flood Fill看一下1和n是否连通(并查集也行),如果连通,说明有路径不需要经过他,则不是必经之点。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

洛谷P1793跑步[NOI导刊]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!