1. 边双连通分量
定义:极大的不包含桥的连通块
无向连通图两个性质:
1° 边连通分量中删除一条边图仍然连通
2° 任意两点之间一定包含两条没有公共边的路径(证明)
3° 任何一个桥的两个端点不一定是割点,比如一条单独的边
2. 点双连通分量
定义:极大的不包含割点的连通块
1° 每个割点都至少属于两个连通分量
2° 两个割点之间的边不一定是桥
综上:点连通分量不一定是边连通分量,边连通分量也不一定是点连通分量,它们之间没有任何关系
3. 如何缩点
在tarjan的过程中如果有x->y的边,且low[y]≥dfn[x](y能到的最上层的点都在x下面),那么如果x是根节点,则x是割点,如果x是根节点,那么至少有两个子节点y满足low[y]≥dfn[x]
Example:
① 冗余路径
将无向图变成边双连通图需要加的边的数量为缩点后叶结点的数量除2向上取整,即cnt/2+1