tarjan 算法与图的连通性

前言与预备知识

发现我根本不会 tarjan，又发现《算法竞赛进阶指南》上正好有相关讲解，于是回来补 tarjan 这个 NOIP 算法。 （顺便颓一会儿水题）

首先我们要知道 搜索树 的相关内容（注意区分搜索树和原图）：

定义 (dfn[cur]) 为 (cur) 节点的时间戳。

(low[cur]) 为 (cur) 节点的追溯值。

其中 (low[cur]) = (min){搜索树中 (cur) 的子树的节点的时间戳， 子树中通过一条边，能够到达的节点的时间戳}

警告：分清 (dfn) 和 (low)！

无向图相关问题

桥 与 边双连通分量

桥

无向图中，如果割掉一条边，可以使整个无向图成为两个连通块，那么这条边成为割边 或 桥。

判定法则：

[low[to] > dfn[cur]
]