题目链接
方法:Tarjan构建边-双连通图
题目分析
题目大意
n
个点,m
条边,希望从任意一个点到另一个点之间都可以有两条路可以走
解析
这题就是poj 3352的加强版,会有重边而已。
这两天正在学习双连通分量的东西,网上搜到了这道题,做一做。
首先,我们为了让他有两条路可以走,那么就等价于将图建成边-双连通图。看到网上的做法,很神奇,将每一个双连通分量先看成一个点,这样,整个图就可以形成一棵树,那么可以统计出树的叶节点的个数leaf,然后两两连边,如果最后有剩余,再连一条边出去即可,共计(left+1)/2
条。
根据Tarjan算法,我们知道在同一个双连通分量中,他们的low值是相同的。那么,我们能不能直接找桥呢?因为桥是树的边。答案是不能!比如一个蝴蝶结的形状|><|
左边的三角形和右边的三角形的low值是不同的,这个图中不存在桥,但是我们无法找到两条完全不重复的路径,因为中间的割点怎么走都会经过,所以我们对于这样的图还要再连一条线。所以我们统计每个分量的入度的时候必须根据low值来确定
然后找出来所有入度为1
的点,总个数位leaf
,结果为(leaf+1)/2
代码
1 |
|