SSOJ2625哪些路不能修
3747+
作者：crxis 发布：2017-12-22 分类：强连通
题目大意：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那就不走，这样有重边也不会走回去了。
程序实现
