双连通分量是指图中每两个点都有两条完全不同的路径可到达..也就是去掉这个图的任意一个边一个点...两两之间依然可达..
图论中的桥...在有向图中是两个连通分量之间唯一的边(如果有多条那么都不是桥)...在无向图中是两个双连通分量之间的唯一边...
而割指的是割点..割点肯定是和桥的端点...但桥的端点不一是割点..如:
(1,4),(2,4),(3,4),(4,5),(4,6),(4,7)都是桥..所有点都是桥的端点...但是只有4是割点...1,2,3,5,6,7都不是割点..
去掉一个连通图中的一个桥或者割点..这个连通图就将成为不连通的多个连通图..
求无向图中的桥的方法是有Tarjan发明的..Byvoid大大的讲解很给力:http://www.byvoid.com/blog/biconnect/
无向图的Tarjan和有向图求强连通分量的Tarjan很像...注意几个不同...
1、没有栈..所以判断时先是看点有没有访问过...else的时候就直接更新Low...不需要再来个判断instack....
2、DFS时不能从 a 递归到了 b..b又马上从a来更新...所以要多加一个notpre..代表递归b时是从哪个点进去的...防止这种情况..
3、Low相等的点在无向图中就是在一个双连通图中...这个比有向图的方便..有向图还需要用栈来维护..通过判断退栈来判断强连通分量..
如果要求桥和割点的话..做完Tarjan..扫描所有的边,有 DFN ( 终点 ) < LOW ( 起点 ) 的边就是桥...这条边的"终点"就是割点..
回到POJ3352...题目给出了连通的无向图..并且两点直接最多只有一条边...求的是加几条边能使得该无向图整个变成一个双连通图..
那么先对图做无向图的Tarjan...得到每个点所在的双连通记录在Low里....可以想象一下..如果把所有的双连通分量分别缩成一个点...那么整个图就是一棵树了..如果给一棵树..要史其成为一个双连通图...那么需要加( 叶子结点数+1)/2调边...
这道题就是在做完Tarjan找作为叶子节点的双连通分量的个数k..然后答案就是(k+1)/2...
Program:
分享到:
相关推荐
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
poj-2528 Mayor's posters 测试数据及答案
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
西北工业大学-c语言-POJ-题目及答案-第七季.doc
北大POJ2002-Squares 解题报告+AC代码
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
算法-炮兵阵地(POJ-1185)(包含源程序).rar
算法-开关问题(POJ-1830)(包含源程序).rar
算法-青蛙的约会(POJ-1061)(包含源程序).rar