POJ 3352 Road Construction ； POJ 3177 Redundant Paths （双联通）

这两题好像是一样的，就是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 （双联通）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。