Content #
时间戳：dfn[u]表示节点u深度优先遍历的序号。追溯点：low[u]表示节点u及其后代所能追溯到的最早（最先被发现）祖先点v的 dfn[v]值，即 \[\begin{diplaymath*} \text{low}[u] = \min_{(u,s),(u,w) \in E}\{\text{dfn}[u], \text{low}[s], \text{dfn}[w]\} \end{displaymath*} \]
其中s是u的儿子，(u, w)是反向边B.
low[u]计算步骤： \[\begin{displaymath*} \text{low}[u] = \begin{cases} \text{dfn}[u] \\ \min\{\text{low}[u], \text{dfn}[w]\} \\ \min\{\text{low}[u],\text{low}[s]\} \end{cases} \end{displaymath*}\]
From #
《算法训练营入门篇》 陈小玉