這兩題好像是一樣的，就是3177要去掉重邊。

但是為什么要去重邊呢？？？？？？我認為如果有重邊的話，應該也要考慮在內才是。

這兩題我用了求割邊，在去掉割邊，用DFS縮點。

有大神說用Tarjan，不過這兩圖好像是無向圖，不過那個求割邊的算法蠻像Tarjan的，不知道那是不是就是Tarjan。

關于雙聯通分量，我還要再去學一下，問題還有很多,比如，點雙聯通，邊雙聯通等等。

我現在只知道：

1.對于無向圖，去掉割邊后，仍然聯通的區域，就是邊雙聯通區域。

2.若要使得任意一棵樹（無向圖），在增加若干條邊后，變成一個邊雙連通圖，那么

至少增加的邊數 =（ 這棵樹總度數為1的結點數 + 1 ）/ 2

?

轉載于:https://www.cnblogs.com/ZGQblogs/p/10139092.html

總結

以上是生活随笔為你收集整理的POJ 3352 Road Construction ； POJ 3177 Redundant Paths （双联通）的全部內容，希望文章能夠幫你解決所遇到的問題。

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