当前位置:首页 > 图论 > 强连通 > 正文
SSOJ2626收费景点
3854+

题目大意:n个点,m条无向边,按照编号从小到大输出所有割点(割顶)。

题目描述

一个旅游胜地,有n个景点、m条双向道路,每一个景点都是一个入口,从每个入口出发,能逛的景点数目是确定的。如果收费才合适?按照景点数目多少来收费太没创意了;每个景点都收费,可能会导致很少人过来游玩;全部景点都免费,那就没有收入。怎么办才好呢?可以在一些关键景点收费!什么是关键景点?所谓关键景点,就是如果不经过这个景点,那么与景点数目表相比,游客至少会少逛2个景点!

输入

第一行两个正整数n和m

接下来m行,每行两个整数a和b,表示景点a和b有一条双向道路

输出

输出所有收费的景点的编号,一行一个,编号小的先输出

样例输入

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

样例输出

4
5

提示

n不超过10万,m不超过n的3倍,n在10个点的数据范围:5, 10, 100, 500, 1000, 5000, 10000, 30000, 50000, 70000, 100000

解题思路

所谓割点,就是图中的一个点,删除他以及跟他相关联的边后,图中的连通块增多。割点都是收费景点,因为删除割点,已经少了一个景点,而且还多了一个连通块,这个连通块原来是能通过割点到达的,现在到不了,即原来能到的景点至少又少1个。收费景点也都是割点,因为不经过他,只会少一个景点,要至少减少2个景点,那么必然要导致至少1个其他景点到不了,即这些景点分离出去即连通块增多。

如何求割点呢?搜索过程中,如果一个点有超过1个“儿子”,那么少了这个点就会让儿子不能相连,连通块增多。如果一个点只有一个“儿子”,自己也是别人的儿子(不是“根”),少了他会导致祖孙不能相连,那么他也是割点。怎么判断是不是儿子呢?如果儿子有返祖边,即能回到该点的祖先,那么不算是儿子,因为少了他,祖孙还可以相连,如果多个儿子都可以回到祖先,那么他们也可以通过祖先相连。为什么要回到祖先,而不是回到自己就行?因为现在要删除的是自己这个点!

深度优先搜索的过程中,需要不断记录每个点的访问情况和深度。如果点没访问过,就继续搜索:搜索完一个点b后,看一下他是否能回到祖先结点,可以的话不算儿子数量;同时,也要更新其父亲a结点的“祖先”,即a能返回到哪个祖先结点;祖先结点深度越小越好,因为只要是父亲结点的祖先,儿子就不算数。如果点已经访问过就不再搜索下去了,单能说明点a能回到祖先结点b,如果b的深度更小,那么a选b作为祖先。

程序实现

About

坚决不Copy代码!

本文标签:,,,

SSOJ2626收费景点:等您坐沙发呢!

发表评论

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