简介

早期生活

计算机科学生涯(算法和数据结构)

奖项

Tarjan的算法介绍(LCA(Tarjan) 强连通分量)

简介

Robert Tarjan，一位计算机科学家，以LCA，强连通分量等算法闻名。

早期生活

Robert Tarjan出生在波莫纳，加利福尼亚州。他的父亲是一个专业儿童精神科医生，以前在国家医院任职。还是孩子的Robert Tarjan就阅读了大量的科学小说，从此对天文学产生兴趣，并梦想成为一名天文学家。他在Scientific American杂志上看完Martin Gardner的数学游戏后又对数学产生了兴趣。他的一位中学老师发现了他对数学的兴趣，从八年级就开始培育他的数学能力。之后Robert开始深入研究数学。

Robert Tarjan上高中就找到了一份工作：从事IBM卡片校对机的工作。 他第一次真正用计算机工作是在1964年，那时他参与Summer Science Program在其中研究天文学。

Robert Tarjan在1969年获得了加州理工学院数学学士学位。在斯坦福大学，他获得了他的计算机科学硕士学位（1971）和博士学位(1972)。在斯坦福，他由罗伯特弗洛伊德和高德纳指导，两位都是非常突出的计算机科学家。他的博士论文是An Efficient Planarity Algorithm。Robert Tarjan选定计算机科学领域作为他的主要研究方向，是因为他认为计算机科学是实践数学理论的方式，有现实价值。

计算机科学生涯

Robert Tarjan自1985年开始任教于普林斯顿大学。 他还在多所大学担任学术职务，如：康奈尔大学（1972-1973年），加州大学伯克利分校（1973-1975），斯坦福大学（1974-1980），纽约大学（1981-1985）。 他也加入过NEC研究所（1989-1997），并在美国麻省理工学院（1996年）担任Visiting Scientist 。Tarjan拥有丰富的商业工作经验：他曾在AT&T贝尔实验室（1980-1989），浩信科技（1997-2001），康柏（2002年）和惠普（2006年至今）工作。 他曾加入ACM和IEEE委员会，并曾为几家期刊的编辑。

算法和数据结构

Robert Tarjan设计了求解的应用领域的许多问题的广泛有效的算法和数据结构。 他已发表了超过228篇理论文章（包括杂志，一些书中的一些章节文章等）。Robert Tarjan以在数据结构和图论上的开创性工作而闻名。 他的一些著名的算法包括 Tarjan最近共同祖先离线算法 ，Tarjan的强连通分量算法 等。其中Hopcroft-Tarjan平面嵌入算法是第一个线性时间平面算法。

Tarjan也开创了重要的数据结构如：斐波纳契堆和splay树（splay发明者还有Daniel Sleator）。另一项重大贡献是分析了并查集。他是第一个证明了计算反阿克曼函数的乐观时间复杂度的科学家。

奖项

Tarjan与约翰霍普克罗夫特共同于1986年获得图灵奖。

Tarjan还于1994年当选为ACM院士。

Tarjan其他奖项包括：

奈望林纳奖信息科学（1983第一个获奖者）

国家科学院的研究倡议奖 （1984）

巴黎Kanellakis奖-理论与实践（ ACM1999）

帕斯卡奖章数学与计算机科学（ 欧洲科学院2004）

加州理工学院杰出校友奖（ 美国加州技术研究所2010）

Tarjan的算法介绍

LCA(Tarjan)

分类，使每个结点都落到某个类中，到时候只要执行集合查询，就可以知道结点的LCA了。

对于一个结点u.类别有:

以u为根的子树、除类一以外的以f(u)为根的子树、除前两类以外的以f(f(u))为根的子树、除前三类以外的以f(f(f(u)))为根的子树……

类一的LCA为u,类二为f(u),类三为f(f(u)),类四为f(f(f(u)))。这样的分类看起来好像并不困难。

但关键是查询是二维的，并没有一个确定的u。接下来就是这个算法的巧妙之处了。

利用递归的LCA过程。

假设lca(u)执行完毕，则以u为根的子树已经全部并为了一个集合。而一个lca的内部实际上做了的事就是对其子结点，依此调用lca.

设v1，v2，v3....vn为u的后继结点且访问顺序为v1,v2,v3...vn

当v1(第一个子结点)被lca，正在处理v2的时候，以v1为根的子树+u同在一个集合里，f(u)+编号比u小的u的兄弟的子树　同在一个集合里，f(f(u))　+　编号比f(u)小的　f(u)的兄弟　的子树　同在一个集合里……

而这些集合，对于v2的LCA都是不同的。因此只要查询x在哪一个集合里，就能知道LCA(v2,x)

还有一种可能，x不在任何集合里。当他是v2的儿子，v3,v4等子树或编号比u大的u的兄弟的子树（等等）时，就会发生这种情况。即还没有被处理。还没有处理过的怎么办？把一个查询(x1,x2)往查询列表里添加两次，一次添加到x1的回答列表里，一次添加到x2的回答列表里，如果在做x1的时候发现 x2已经被处理了，那就接受这个询问，未被处理就忽略。（两次中必定只有一次询问被接受）.

复杂度为O（n+Qusetion times）Qusetion times为询问次数

实现用并查集

伪代码如下：

//parent为并查集，FIND为并查集的查找操作

//QUERY为询问结点对集合

//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代码：

#include<iostream>

#include<vector>

using namespace std;

const int MAX=10001;

int f[MAX];

int r[MAX];

int indegree[MAX];//保存每个节点的入度

int visit[MAX];

vector<int> tree[MAX],Qes[MAX];

int ancestor[MAX];

void init(int n)

{

for(int i=1;i<=n;i++)

{

r[i]=1;

f[i]=i;

indegree[i]=0;

visit[i]=0;

ancestor[i]=0;

tree[i].clear();

Qes[i].clear();

}

}

int find(int n)

{

if(f[n]==n)

return n;

else

f[n]=find(f[n]);

return f[n];

}//查找函数，并压缩路径

int Union(int x,int y)

{

int a=find(x);

int b=find(y);

if(a==b)

return 0;

//相等的话,x向y合并

else if(r[a]<=r[b])

{

f[a]=b;

r[b]+=r[a];

}

else

{

f[b]=a;

r[a]+=r[b];

}

return 1;

}//合并函数，如果属于同一分支则返回0，成功合并返回1

void LCA(int u)

{

ancestor[u]=u;

int size = tree[u].size();

for(int i=0;i<size;i++)

{

LCA(tree[u][i]);

Union(u,tree[u][i]);

ancestor[find(u)]=u;

}

visit[u]=1;

size = Qes[u].size();

for(int i=0;i<size;i++)

{

//如果已经访问了问题节点,就可以返回结果了.

if(visit[Qes[u][i]]==1)

{

cout<<ancestor[find(Qes[u][i])]<<endl;

return;

}

}

}

int main()

{

int cnt;

int n;

cin>>cnt;

while(cnt--)

{

cin>>n;;

init(n);

int s,t;

for(int i=1;i<n;i++)

{

cin>>s>>t;

tree[s].push_back(t);

indegree[t]++;

}

//这里可以输入多组询问

cin>>s>>t;

//相当于询问两次

Qes[s].push_back(t);

Qes[t].push_back(s);

for(int i=1;i<=n;i++)

{

//寻找根节点

if(indegree[i]==0)

{

LCA(i);

break;

}

}

}

return 0;

}

强连通分量

首先我们把强连通分量看做一个齿轮或环（他会转啊），不考虑其他的限制则可认为分量结点可以互换（就是转一下）不会影响分量中包含的结点（为什么这么想呢？你理解tarjan时中的low值有帮助）

如图（分量为S）：Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，

Low(u)=Min

{ DFN(u), Low(v),(u,v)为树枝边，u为v的父节点 DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)}当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

伪代码：tarjan(u){

DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值

Stack.push(u) // 将节点u压入栈中

for each (u, v) in E // 枚举每一条边

if (v is not visted) // 如果节点v未被访问过

tarjan(v) // 继续向下找

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

else if (v in S) // 如果节点v还在栈内

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

if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根

repeat

v = S.pop // 将v退栈，为该强连通分量中一个顶点

print v

until (u== v)}

cpp：

void tarjan(int i)

{

int j;

DFN[i]=LOW[i]=++Dindex;

instack[i]=true;

Stap[++Stop]=i;

for (edge *e=V[i];e;e=e->next)

{

j=e->t;

if (!DFN[j])

{

tarjan(j);

if (LOW[j]<LOW[i])

LOW[i]=LOW[j];

}

else if (instack[j] && DFN[j]<LOW[i])

LOW[i]=DFN[j];

}

if (DFN[i]==LOW[i])

{

Bcnt++;

do

{

j=Stap[Stop--];

instack[j]=false;

Belong[j]=Bcnt;

}

while (j!=i);

}

}

void solve()

{

int i;

Stop=Bcnt=Dindex=0;

memset(DFN,0,sizeof(DFN));

for (i=1;i<=N;i++)

if (!DFN[i])

tarjan(i);

}

pascal：procedure dfs(s:longint);

var ne:longint;

begin

view[s]:=1; //view[i]表示点i的访问状态.未访问,正访问,已访问的点,值分别为0,1,2

inc(top);stack[top]:=s; //当前点入栈

inc(time);rea[s]:=time;low[s]:=time; //记录访问该点的真实时间rea和最早时间low

ne:=head[s];

while ne<>0 do begin

if view[e[ne]]=0 then dfs(e[ne]); //如果扩展出的点未被访问,继续扩展

if view[e[ne]]<2 then low[s]:=min(low[s],low[e[ne]]);

//如果扩展出的不是已访问的点,更新访问源点s的最早时间.

//容易理解,如果一个点能到达之前访问过的点,那么路径中存在一个环使它能更早被访问

ne:=next[ne];

end;

if rea[s]=low[s] then begin //如果s的最早访问时间等于其实际访问时间,则可把其视作回路的"始点"

inc(tot); //连通块编号

while stack[top+1]<>s do begin //将由s直接或间接扩展出的点标记为同一连通块,标记访问后出栈

lab[stack[top]]:=tot; //lab[i]表示点i所属的连通块

view[stack[top]]:=2;

dec(top);

end;

end;

end;