Robert Tarjan他還在多所大學(xué)擔(dān)任學(xué)術(shù)職務(wù)，如：康奈爾大學(xué)（1972-1973年），加州大學(xué)伯克利分校（1973-1975），斯坦福大學(xué)（1974-1980），紐約大學(xué)（1981-1985）。 他也加入過NEC研究所（1989-1997），并在美國(guó)麻省理工學(xué)院（1996年）擔(dān)任Visiting Scientist 。

Tarjan：他曾在AT&T貝爾實(shí)驗(yàn)室（1980-1989），浩信科技（1997-2001），康柏（2002年）和惠普（2006年至今）工作。 他曾加入ACM和IEEE委員會(huì)，并曾為幾家期刊的編輯。

Robert Tarjan出生在波莫納，加利福尼亞州。他的父親是一個(gè)專業(yè)兒童精神科醫(yī)生，以前在國(guó)家醫(yī)院任職。還是孩子的Robert Tarjan就閱讀了大量的科學(xué)小說，從此對(duì)天文學(xué)產(chǎn)生興趣，并夢(mèng)想成為一名天文學(xué)家。他在Scientific American雜志上看完Martin Gardner的數(shù)學(xué)游戲后又對(duì)數(shù)學(xué)產(chǎn)生了興趣。他的一位中學(xué)老師發(fā)現(xiàn)了他對(duì)數(shù)學(xué)的興趣，從八年級(jí)就開始培育他的數(shù)學(xué)能力。之后Robert開始深入研究數(shù)學(xué)。

Robert Tarjan上高中就找到了一份工作：從事IBM卡片校對(duì)機(jī)的工作。 他第一次真正用計(jì)算機(jī)工作是在1964年，那時(shí)他參與Summer Science Program在其中研究天文學(xué)。

Robert Tarjan在1969年獲得了加州理工學(xué)院數(shù)學(xué)學(xué)士學(xué)位。在斯坦福大學(xué)，他獲得了他的計(jì)算機(jī)科學(xué)碩士學(xué)位（1971）和博士學(xué)位(1972)。在斯坦福，他由羅伯特·弗洛伊德和高德納指導(dǎo)，兩位都是非常突出的計(jì)算機(jī)科學(xué)家。他的博士論文是An Efficient Planarity Algorithm。Robert Tarjan選定計(jì)算機(jī)科學(xué)領(lǐng)域作為他的主要研究方向，是因?yàn)樗�認(rèn)為計(jì)算機(jī)科學(xué)是實(shí)踐數(shù)學(xué)理論的方式，有現(xiàn)實(shí)價(jià)值。

Robert Tarjan設(shè)計(jì)了求解的應(yīng)用領(lǐng)域的許多問題的廣泛有效的算法和數(shù)據(jù)結(jié)構(gòu)。 他已發(fā)表了超過228篇理論文章（包括雜志，一些書中的一些章節(jié)文章等）。Robert Tarjan以在數(shù)據(jù)結(jié)構(gòu)和圖論上的開創(chuàng)性工作而聞名。 他的一些著名的算法包括 Tarjan最近共同祖先離線算法，Tarjan的強(qiáng)連通分量算法 以及Link-Cut-Trees算法等。其中Hopcroft-Tarjan平面嵌入算法是第一個(gè)線性時(shí)間平面算法。

Tarjan也開創(chuàng)了重要的數(shù)據(jù)結(jié)構(gòu)如：斐波納契堆和splay樹（splay發(fā)明者還有Daniel Sleator）。另一項(xiàng)重大貢獻(xiàn)是分析了并查集。他是第一個(gè)證明了計(jì)算反阿克曼函數(shù)的樂觀時(shí)間復(fù)雜度的科學(xué)家。

Tarjan與約翰霍普克羅夫特共同于1986年獲得圖靈獎(jiǎng)。

Tarjan還于1994年當(dāng)選為ACM院士。

Tarjan其他獎(jiǎng)項(xiàng)包括：

奈望林納獎(jiǎng)信息科學(xué)（1983第一個(gè)獲獎(jiǎng)?wù)撸?/p>

國(guó)家科學(xué)院的研究倡議獎(jiǎng) （1984）

巴黎Kanellakis獎(jiǎng)-理論與實(shí)踐（ ACM1999）

帕斯卡獎(jiǎng)?wù)聰?shù)學(xué)與計(jì)算機(jī)科學(xué)（歐洲科學(xué)院2004）

加州理工學(xué)院杰出校友獎(jiǎng)（ 美國(guó)加州技術(shù)研究所2010）

LCA(Tarjan)

分類，使每個(gè)結(jié)點(diǎn)都落到某個(gè)類中，到時(shí)候只要執(zhí)行集合查詢，就可以知道結(jié)點(diǎn)的LCA了。

對(duì)于一個(gè)結(jié)點(diǎn)u.類別有:

以u(píng)為根的子樹、除類一以外的以f(u)為根的子樹、除前兩類以外的以f(f(u))為根的子樹、除前三類以外的以f(f(f(u)))為根的子樹……

類一的LCA為u,類二為f(u),類三為f(f(u)),類四為f(f(f(u)))。這樣的分類看起來好像并不困難。

但關(guān)鍵是查詢是二維的，并沒有一個(gè)確定的u。接下來就是這個(gè)算法的巧妙之處了。

利用遞歸的LCA過程。

假設(shè)lca(u)執(zhí)行完畢，則以u(píng)為根的子樹已經(jīng)全部并為了一個(gè)集合。而一個(gè)lca的內(nèi)部實(shí)際上做了的事就是對(duì)其子結(jié)點(diǎn)，依此調(diào)用lca.

設(shè)v1，v2，v3....vn為u的后繼結(jié)點(diǎn)且訪問順序?yàn)関1,v2,v3...vn

當(dāng)v1(第一個(gè)子結(jié)點(diǎn))被lca，正在處理v2的時(shí)候，以v1為根的子樹+u同在一個(gè)集合里，f(u)+編號(hào)比u小的u的兄弟的子樹　同在一個(gè)集合里，f(f(u))　+　編號(hào)比f(wàn)(u)小的　f(u)的兄弟　的子樹　同在一個(gè)集合里……

而這些集合，對(duì)于v2的LCA都是不同的。因此只要查詢x在哪一個(gè)集合里，就能知道LCA(v2,x)

還有一種可能，x不在任何集合里。當(dāng)他是v2的兒子，v3,v4等子樹或編號(hào)比u大的u的兄弟的子樹（等等）時(shí)，就會(huì)發(fā)生這種情況。即還沒有被處理。還沒有處理過的怎么辦？把一個(gè)查詢(x1,x2)往查詢列表里添加兩次，一次添加到x1的回答列表里，一次添加到x2的回答列表里，如果在做x1的時(shí)候發(fā)現(xiàn) x2已經(jīng)被處理了，那就接受這個(gè)詢問，未被處理就忽略。（兩次中必定只有一次詢問被接受）.

復(fù)雜度為O（n+Qusetion times）Qusetion times為詢問次數(shù)

若需更加詳細(xì)，還可到“tarjan算法”處看看

實(shí)現(xiàn)用并查集

偽代碼如下：

//parent為并查集，F(xiàn)IND為并查集的查找操作

//QUERY為詢問結(jié)點(diǎn)對(duì)集合

//TREE為基圖有根樹

Tarjan(u)

visit[u] = true

for each (u, v) in QUERY

if visit[v]

ans(u, v) = FIND(v)

for each (u, v) in TREE

if !visit[v]

Tarjan(v)

parent[v] = u

cpp代碼：

強(qiáng)連通分量

首先我們把強(qiáng)連通分量看做一個(gè)齒輪或環(huán)（他會(huì)轉(zhuǎn)�。�，不考慮其他的限制則可認(rèn)為分量結(jié)點(diǎn)可以互換（就是轉(zhuǎn)一下）不會(huì)影響分量中包含的結(jié)點(diǎn)（理解tarjan時(shí)中的low值有幫助）

如圖（分量為S）：

Tarjan算法是基于對(duì)圖深度優(yōu)先搜索的算法，每個(gè)強(qiáng)連通分量為搜索樹中的一棵子樹。搜索時(shí)，把當(dāng)前搜索樹中未處理的節(jié)點(diǎn)加入一個(gè)堆棧，回溯時(shí)可以判斷棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量。

定義DFN(u)為節(jié)點(diǎn)u搜索的次序編號(hào)(時(shí)間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號(hào)。由定義可以得出，

Low(u)=Min

{ DFN(u), Low(v),(u,v)為樹枝邊，u為v的父節(jié)點(diǎn) DFN(v),(u,v)為指向棧中節(jié)點(diǎn)的后向邊(非橫叉邊)}當(dāng)DFN(u)=Low(u)時(shí)，以u(píng)為根的搜索子樹上所有節(jié)點(diǎn)是一個(gè)強(qiáng)連通分量。

偽代碼：tarjan(u){

DFN[u]=Low[u]=++Index // 為節(jié)點(diǎn)u設(shè)定次序編號(hào)和Low初值

Stack.push(u) // 將節(jié)點(diǎn)u壓入棧中

for each (u, v) in E // 枚舉每一條邊

if (v is not visted) // 如果節(jié)點(diǎn)v未被訪問過

tarjan(v) // 繼續(xù)向下找

Low[u] = min(Low[u], Low[v])

else if (v in S) // 如果節(jié)點(diǎn)v還在棧內(nèi)

Low[u] = min(Low[u], DFN[v])

if (DFN[u] == Low[u]) // 如果節(jié)點(diǎn)u是強(qiáng)連通分量的根

repeat

v = S.pop // 將v退棧，為該強(qiáng)連通分量中一個(gè)頂點(diǎn)

print v

until (u== v)}

c/c++：

pascal：