day 9 tarjan 算法总结

day 9 tarjan 算法总结

首先，在学习 tarjan 之前需要知道的几个定义。

• 树边：搜索树上的边。
• 前向边：从祖先指向后代的边。
• 返祖边：从后代指向祖先的边。
• 横向边：上述以外的边。

在 dfs 搜索一张无向图时，得到的树一定不含横向边。

tarjan 的过程：

对于每个未访问的节点，遍历其搜索树，同时用栈来存储访问到的点，在搜索时需要记录以下两个信息：

• $df{n}_u$ 为节点 $u$ 的 dfs 序。
• $lo{w}_u$ 为 $u$ 或 $u$ 的子树节点，只经过一条非树边，能够追溯到的最小的 $dfn$，形式话说，把 $dfn$ 当做一个时间轴，编号为几，就是此节点在搜索时是第几个被搜索到的。$low$ 也就表示这个节点通过最多一条非树边能够达到的 $dfn$ 序最小的节点。

$dfn$ 我们都知道是在 dfs 遍历中更新的，所以重点是 $low$ 数组如何更新，我们设当前遍历到了点 $x$：

• 初始情况下显然，$lo{w}_x=df{n}_x$，最小能够遍历到的目前肯定最小是当前的 dfs 序。
• 对于有向边 $(x,y)$，如果点 $y$ 已经走过，说明这是一条非树边，因为树边肯定是按照顺序来遍历的，不会已经遍历过点 $y$ 而没有走过点 $x$。那么就用 $y$ 的 $dfn$ 序来更新点 $x$ 的 $low$，显然能够得来公式，即 $lo{w}_x=\min (lo{w}_x,df{n}_y)$。
• 对于有向边 $(x,y)$，如果 $y$ 还没有到达，说明是一条树边，道理就和上面的差不多，那么继续 dfs，回溯之后，我们显然能够得出点 $y$ 能够达到的最小 $dfn$ 序，点 $x$ 也能够达到，所以得出公式，即 $lo{w}_x$