例4

例4 嗅探器

嗅探器

给出一无向图连通图，以及图上的两点 $a$ 和 $b$，求删掉哪个点以后，可使得 $a$、$b$ 分别位于不同的连通块？

所求点 $u$ 为割点，且删掉 $u$ 之后，$a$、$b$ 分别位于不同的连通块。 因此，我们从点 $a$ 开始执行 tarjan 求割点算法，如果找到的割点位于 $a$ 到 $b$ 的路径中，那么该割点便满足条件。

如何保证割点 $u$ 位于 $a$、$b$ 之间的路径呢？假设我们是通过 $u$ 的儿子节点为 $v$ 判定 $u$ 为割点，那么，若满足条件

$dfn[v] \le dfn[b]$

便意味着 $u$ 位于 $a$、$b$ 之间。这是因为 $dfn[b]$ 的值不是 $0$，说明已经搜过点 $b$，其值大于等于 $dfn[v]$，说明先访问的 $v$，再访问的 $b$。所以 $b$ 一定位于子树 $v$。