????Robert Tarjan,計(jì)算機(jī)科學(xué)家，以LCA、強(qiáng)連通分量等算法而聞名。Tarjan設(shè)計(jì)了求解的應(yīng)用領(lǐng)域的廣泛有效的算法和數(shù)據(jù)結(jié)構(gòu)。他以在數(shù)據(jù)結(jié)構(gòu)和圖論上的開(kāi)創(chuàng)性工作而聞名，他的一些著名的算法有Tarjan最近公共祖先離線算法，Tarjan的強(qiáng)連通分量算法以及Link-Cut-Trees算法等。其中Hopcroft-Tarjan平面嵌入算法是第一個(gè)線性時(shí)間平面算法。Tarjan也開(kāi)創(chuàng)了重要的數(shù)據(jù)結(jié)構(gòu)如：斐波那契堆和splay樹(shù)，另一項(xiàng)重大貢獻(xiàn)是分析了并查集。他是第一個(gè)證明了計(jì)算反阿克曼函數(shù)的樂(lè)觀時(shí)間復(fù)雜度的科學(xué)家。

基本概念：

????時(shí)間戳：dfn[u]表示u結(jié)點(diǎn)深度優(yōu)先遍歷的序號(hào)。

????追溯點(diǎn)： low[u]表示u結(jié)點(diǎn)或u的子孫能通過(guò)非父子邊追溯到的dfn最小的結(jié)點(diǎn)序號(hào)，即回到最早的過(guò)去。

? ? 那么4號(hào)結(jié)點(diǎn)能回到最早的過(guò)去是1號(hào)結(jié)點(diǎn)（dfn=1），因此low[4] = min(low[4],dfn[1])=1。

上圖中加粗紅色箭頭表示深度優(yōu)先搜索樹(shù)，起點(diǎn)就是樹(shù)根。

1.無(wú)向圖的橋與割點(diǎn)

橋判定法則：

割點(diǎn)判定法則：

2.有向圖的強(qiáng)連通分量