今天想看看关于桥的求法，搜到了这样一个题，由与网上缺少相关的资料，花了很多时间在找资料上，最后发现lrj的书上有这个问题的描述:

　　无向图的割点和桥（见lrj书）

　　算法基于以下原理：（1）如果根顶点的儿子数大于1，则根顶点是割点（2）如果一个点和这个点的子孙都不存在指向这个点祖先的后向边，则这个点为割点。实现时需要对每个结点记录一个low值，表示该结点的子孙能够到达的最小的深度，如果这个值小于或等于该点的深度，则该点为割点。如果

　　y是x的儿子并且y的low值大于x的深度，则边(x,y)为图的桥。

　　原来求割点和求割边是同一回事，难怪网上只有割点的资料，割边的几乎没有提及。具体的算法看lrj的书，这里说一下做题的心得。

　　主要是两个方面：

　　1。题目中给出的图是有重边的，如何判断重边？这个问题很重要根据题意，没法确定重边中的那一条边会被烧掉，所以重边一定不是我们想要的结果，要从求出的桥里面剔除。我想了比较长的时间，开矩阵吧，10000*10000的矩阵虽然定位是O(1)的，但是这么大的矩阵肯定爆。

　　所以只能用邻接表。可邻接表如何判重，难道线性扫描一遍？每一次加边都要从表头扫到表尾，然后才能实现插入，最坏的情况是0+1+2+3+...+m-1=O(m^2)。（当然这有点极端，毕竟n只有10000级别，是边的十分之一）建立邻接表的复杂度就有点。。。另外 20个case。。。

　　但是事实上，这道题我就是这么做的，邻接表+内存池，线性扫描判重，用的时间大约是时限的五分之一。。。可以接受。。。

　　2。这个题中给出的是无向边，建邻接表的时候正反都要建，但是一但正向被搜索过，方向就定了，DFS的过程实际就是将一个无向图，转换成一个有根的有向的深度优先生成树的过程。所以，每考察一个节点就要记录下他的父亲节点，不能将父子边当成回边，这个要特别注意。然后就是