边双联通分量与割边

程序员文章站 2022-04-23 23:28:59

前言在图论中，除了在有向图中的强连通分量，在无向图中还有一类双联通分量双联通分量一般是指点双连通分量当然，还有一种叫做边双连通分量边双联通分量对于一个连通图，如果任意两点至少存在两条“边不重复”的路径，则说图是点双连通的，边双连通的极大子图称为边双连通分量。边双联通分量的计算方法比较 ......

前言

在图论中，除了在有向图中的强连通分量，在无向图中还有一类双联通分量

双联通分量一般是指点双连通分量

当然，还有一种叫做边双连通分量

对于一个连通图，如果任意两点至少存在两条“边不重复”的路径，则说图是点双连通的，边双连通的极大子图称为边双连通分量。

边双联通分量的计算方法比较简单

类比tarjan求强联通分量的算法，唯一的区别在于不能沿着dfs过来的那条边走回去。

也就是说在tarjan的时候我们需要记录一下父亲节点

其余的就和普通的tarjan一样啦

割边：对于无向图中的边\(i\)，若去掉\(i\)，无向图的联通快个数会增加，则称点\(i\)为割边(桥)

计算方法

不难发现一条边是割边当且仅当他不在任何一个边双里。

也就是说当\(low[v]>dfn[u]\)时\((u,v)\)就是一条割边。