題目鏈接：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/

?

?

?

總結

以上是生活随笔為你收集整理的poj 1515+poj 1438(边双连通)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。