[学习笔记]tarjan求割边

上午打模拟赛的时候想出了第三题题解,可是我不会 $tarjan$ 求割边只能暴力判割边了QAQ

所以,本文介绍 $tarjan$ 求割边(又称桥).

$dfn[;],low[;]$ 的定义同 $tarjan$ 求有向图强连通分量.

枚举当前点 $u$ 的所有邻接点 $v$ :

1.如果某个邻接点 $v$ 未被访问过,则访问 $v$ ,并在回溯后更新 $low[u]=min(low[u],low[v]);$

2.如果某个邻接点 $v$ 已被访问过，则更新 $low[u]=min(low[u],dfn[v]).$

对于当前节点 $u$ ,如果邻接点中存在一点 $v$ 满足 $low[v]>dfn[u]$ ( $v$ 向上无法到达 $u$ 及 $u$ 祖先)说明 $(u,v)$ 为一条割边.

inline void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dfn[e[i].to]){
            tarjan(e[i].to,u);
            low[u]=min(low[u],low[e[i].to]);
            if(low[e[i].to]>dfn[u]) cut[e[i].n]=true; 
        }
        else if(e[i].to!=fa)
            low[u]=min(low[u],dfn[e[i].to]);
}