数据结构与算法_Tarjan算法

    Robert Tarjan,计算机科学家，以LCA、强连通分量等算法而闻名。Tarjan设计了求解的应用领域的广泛有效的算法和数据结构。他以在数据结构和图论上的开创性工作而闻名，他的一些著名的算法有Tarjan最近公共祖先离线算法，Tarjan的强连通分量算法以及Link-Cut-Trees算法等。其中Hopcroft-Tarjan平面嵌入算法是第一个线性时间平面算法。Tarjan也开创了重要的数据结构如：斐波那契堆和splay树，另一项重大贡献是分析了并查集。他是第一个证明了计算反阿克曼函数的乐观时间复杂度的科学家。

基本概念：

    时间戳：dfn[u]表示u结点深度优先遍历的序号。

    追溯点： low[u]表示u结点或u的子孙能通过非父子边追溯到的dfn最小的结点序号，即回到最早的过去。

    那么4号结点能回到最早的过去是1号结点（dfn=1），因此low[4] = min(low[4],dfn[1])=1。

上图中加粗红色箭头表示深度优先搜索树，起点就是树根。

1.无向图的桥与割点

桥判定法则：

割点判定法则：

2.有向图的强连通分量