边双联通分量与割边
程序员文章站
2022-07-10 17:54:39
前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双联通分量 双联通分量一般是指 点双连通分量 当然,还有一种叫做 边双连通分量 边双联通分量 对于一个连通图,如果任意两点至少存在两条“边不重复”的路径,则说图是点双连通的,边双连通的极大子图称为边双连通分量。 边双联通分量的计算方法比较 ......
前言
在图论中,除了在有向图中的强连通分量,在无向图中还有一类双联通分量
双联通分量一般是指点双连通分量
当然,还有一种叫做边双连通分量
边双联通分量
对于一个连通图,如果任意两点至少存在两条“边不重复”的路径,则说图是点双连通的,边双连通的极大子图称为边双连通分量。
边双联通分量的计算方法比较简单
类比tarjan求强联通分量的算法,唯一的区别在于不能沿着dfs过来的那条边走回去。
也就是说在tarjan的时候我们需要记录一下父亲节点
其余的就和普通的tarjan一样啦
割边(桥)
割边:对于无向图中的边\(i\),若去掉\(i\),无向图的联通快个数会增加,则称点\(i\)为割边(桥)
计算方法
不难发现一条边是割边当且仅当他不在任何一个边双里。
也就是说当\(low[v]>dfn[u]\)时\((u,v)\)就是一条割边。