10929解题报告(ailyanlu提供)

yiyiyi4321

http://acm.hnu.cn:8080/online/?a ... 0929&courseid=0
本题的题意是要在一个强连通的有向图里面将尽可能多的双向边改成单向边，同时必须保持图的强连通性。有向图的强连通性是指图中任意两点之间都有路径可达。解决本题的关键就是利用图的深度优先生成树的性质。
<1>. 图的深度优先生成树
对一个强连通的有向图来说，从任意一点出发，都可以通过深度优先沿着图中的边遍历图中其它所有的点。这个遍历的过程可以表示成为一棵树的形式，就是该图的一棵深度优先生成树。如果按照扩展点的先后次序将所有点排成一个序列，就得到该树的前序遍历。



有向图
<2>. 首先找出所有不可以改向的双向边。
显然并不是所有的双向边都可以进行改向，某些边一旦被改向，就无法再保持图的强连通性。例如在上图中，边<1,.3>就不可以改向。我们不妨把这种边称为有向图的割边。给原图中所有的单向边增加一条反向的虚边，使所有的边都变成双向边，则原图就变成一个无向图。可以证明原图中的割边在新图中还是割边，而且增加虚边的过程不会在新图中引入新的割边。
证明其实只要注意到，这个是一个强连通图就可以了。因为所有的单向边都不能做为桥，只有双向边才能作为桥。所以求出新图中的所有割边，也就求出了原图的所有割边。对于无向图，其割边可以通过深度优先生成树来求出，算法复杂度为O(n^2).具

<3> 很明显，如果不是桥的双向边，由图的强连通性，那么这个边是应该在一个有向圈中
证明也比较简单。。。

ailyanlu

。。。。。发觉竟然有我的东西。。。