poj 1515+poj 1438(边双连通)

题目链接:http://poj.org/problem?id=1515

思路:题目的意思是说将一个无向图改成有向图,使其成为强连通,输出所有的边。我们可以求无向图的边双连通分量,对于同一个双连通分量,只需保留单边即可构成强连通,而不同的双连通分量则需保留双向边。

http://paste.ubuntu.com/5965998/

1438是1515的加强版:http://poj.org/problem?id=1438

题目大意是将一个混合图(有无向边和有向边)改成强连通图,并且只能去掉某些无向边和有向边。这里我们可以把有向边看成无向边,然后求边双连通分量,对于那些桥,必须加边,对于同一个连通分量,在访问的同时定向,对于有向边,如果访问的方向相反,那么就不予以访问,这样在每条边(假设是now -> v)进行完low的函数计算的时候(其实是计算low[v]),我们都会判一次是否会有low[v] > low[now],如果上述关系式成立,那就说明按照现在的定向方法,v是不能访问到它的前驱的,所以对于当前边,就对它取反向,这样当前的v节点就可以访问到前驱节点了,因为这个连通分支原来就是双联通的(将边全部看成无向边),所以对当前边的改变,不会影响v的前驱节点到v的连通性,这样就图就成强连通了。

http://paste.ubuntu.com/5966330/

原文地址:https://www.cnblogs.com/wally/p/3248923.html