当前位置:首页 > 图论 > 强连通 > 正文
SSOJ2625哪些路不能修
2793+

题目大意:n个点,m条双向边,删除哪些边会导致连通块变小?

题目描述

一个有n个景点(入口)、m条单向道路的旅游胜地,单向是不友好的,因为这会让游客走很多冤枉路,而且从同一个入口出发,往不同方向走,能游玩的景点数目可能不同。于是,善良的Bob决定将道路全部改造成双向的,让每一个入口能逛的景点数量都确定下来,并制作景点数目表,让游客清楚地知道各个入口的景点数。但是,如果后面还需要修路,就可能导致景点数目不一致。如果要景点数目表正确,请问哪些路是不能修的?

输入

第一行两个正整数n和m

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

输出

输出所有不能修的道路,按照原来边的编号从小到大的顺序输出,一行一个

样例输入

7 8
1 7
7 6
6 1
6 5
5 2
5 4
2 4
3 4

样例输出

6 5
3 4

提示

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

解题思路

如果没有环,那么每一条边都是桥。如何把环去掉呢?缩点!把环缩成一个点。与有向图求强连通分量相似,只是无向图中,一条边有两个方向,一个方向走过后,另外一个方向就不可以走了,这样才能保证每条边只访问一次,确保遇到访问中的点是环中的点。代码中用u数组记录边的编号是否用过,如果用过就不能再使用了,这样可以去除双向边的影响,因为双向边也是一个环。如果题目要求不算重边,那就要用另外一种方法:dfs(int a, int p),其中a是当前点,p是前一个点,b是下一个点,如果b==p那就不走,这样有重边也不会走回去了。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2625哪些路不能修:等您坐沙发呢!

发表评论

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