tarjan，tarjan算法为什么low

本文目录一览

1，tarjan算法为什么low
2，tarjan做LCA是不是很慢
3，最近公共祖先的算法
4，强连通分量的Tarjan算法思路
5，C Tarjan到底干嘛的怎么写
6，求最近公共祖先的tarjan算法pascal标程

1，tarjan算法为什么low

tarjan主要时间是用在RMQ的构建上，即遍历树，然后构造遍历数组，构造RMQ序列。这里的时间复杂度大约是O(2*n*log(2*n))。而对于一个询问，处理速度大约是O(1)，即从RMQ序列中查询相应节点的位置，以及对比操作。

没看懂什么意思？

tarjan算法为什么low

2，tarjan做LCA是不是很慢

不是，tarjan是正常人写的算法中最快的。LCA可以经过两次转化后做到O(n)，但是这样没有太大实际意义，因为并查集的复杂度并不比这个大。

每深搜到一个节点，都把与这个节点相关的查询都处理掉了（包含有当前节点的查询），并不是所有的q个查询所以总和是q而不是每个节点都是q

这个还慢吗？可能是DFS调用栈的耗时比较多吧……

tarjan做LCA是不是很慢

3，最近公共祖先的算法

利用并查集优越的时空复杂度，我们可以实现LCA问题的O(n+Q)算法，这里Q表示询问的次数。Tarjan算法基于深度优先搜索的框架，对于新搜索到的一个结点，首先创建由这个结点构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外，这时把子树所形成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树，直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的，同时可以处理有关当前结点的LCA询问，如果有一个从当前结点到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点与v的最近公共祖先一定还没有被检查，而这个最近公共祖先的包涵v的子树一定已经搜索过了，那么这个最近公共祖先一定是v 所在集合的祖先。下面给出这个算法的伪代码描述： LCA(u)d[i] 表示 i节点的深度, p[i,j] 表示 i 的 2^j 倍祖先那么就有一个递推式子 p[i,j]=p[p[i,j-1],j-1]这样子一个O(NlogN)的预处理求出每个节点的 2^k 的祖先然后对于每一个询问的点对a, b的最近公共祖先就是：先判断是否 d[a] > d[b] ,如果是的话就交换一下(保证 a 的深度小于 b 方便下面的操作)然后把b 调到与a 同深度, 同深度以后再把a, b 同时往上调(dec(j)) 调到有一个最小的j 满足p[a,j]!=p[b,j] (a b 是在不断更新的), 最后再把 a, b 往上调 (a=p[a,0], b=p[b,0]) 一个一个向上调直到a = b, 这时 a or b 就是他们的最近公共祖先

最近公共祖先的算法

4，强连通分量的Tarjan算法思路

这个算法思路不难理解，由开篇第一句话可知，任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么其实，我们只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。那么剩下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。那么如何确定强连通分量的根，在这里我们维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根，为什么呢？因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。至于如何拿出强连通分量，这个其实很简单，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。现在知道如何拿出了强连通分量了吧？是的，因为当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗？假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。现在没有疑问了吧，那么算法介绍就完了。

5，C Tarjan到底干嘛的怎么写

Tarjan算法是用来求有向图的强连通分量的。这是c++代码，　　#define M 50//题目中可能的最大点数　　intSTACK[M],top=0;//Tarjan算法中的栈　　boolInStack[M];//检查是否在栈中　　intDFN[M];//深度优先搜索访问次序　　intLow[M];//能追溯到的最早的次序　　intComponentNumber=0;//有向图强连通分量个数　　intIndex=0;//索引号　　vectorEdge[M];//邻接表表示　　vectorComponent[M];//获得强连通分量结果　　intInComponent[M];//记录每个点在第几号强连通分量里　　intComponentDegree[M];//记录每个强连通分量的度　　voidTarjan(inti){intj; 　　DFN[i]=Low[i]=Index++; 　　InStack[i]=true; 　　STACK[++top]=i; 　　for(inte=0;e 　　{ 　　　j=Edge[i][e]; 　　　if(DFN[j]==-1) 　　　{ 　　　　Tarjan(j); 　　 Low[i]=min(Low[i],Low[j]); 　　　} 　　　else if(InStack[j]) 　　　　Low[i]=min(Low[i],Low[j]); 　　} 　　if(DFN[i]==Low[i]) 　　{ 　　　　ComponentNumber++; 　　　　do{ 　　　　j=STACK[top--]; 　　　　InStack[j]=false; 　　　　Component[ComponentNumber].push_back(j); 　　　　InComponent[j]=ComponentNumber; 　　　　}while(j!=i); 　　}

在c语言中return 表示从被调函数返回到主调函数继续执行，返回时可附带一个返回值，由return后面的参数指定。　　因此，在c语言中一般出现return语句，即改变程序执行流程到母函数中，因此无论是在if语句还是while语句，还是其它的什么语句，return始终是返回母函数的调用，不需要细分什么情况。

6，求最近公共祖先的tarjan算法pascal标程

首先从顶点a出发，沿父指针将a至根的路径上的所有顶点设访问标志。然后从b顶点出发，沿父指针追溯到第1个已访问的顶点b，该顶点即为a和b的最近公共祖先。var n,rt,a,b,i:integer;l,r,pt:array[0..max]of integer; vt:array[1..max]of boolean; readln(f,n,rt); for i:=1 to n do begin readln(l[i],r[i]); if i=rt then pt[rt]:=0 else pt[l[i]]:=i; pt[r[i]]:=i end; readln(a,b); while a*b<>0 do begin fillchar(vt,sizeof(vt),0); repeat vt[a]:=true;a:=pt[a] until a=0; while not vt[b] do b:=pt[b]; writeln(b);readln(a,b);End;

代码可能比较长，不要介意。思路：从根节点开始找，每次用深度优先搜索的方法遍历儿子节点，如果遍历到2个节点在该节点的两个子树集合里，则该点就是他们的lca。具体方法：首先遍历第一个子树，如果遍历到了其中一个节点，另一个节点已经遍历到了，那么对改点做一次找祖先。每个子树都这么做。如果没有找到就将改点的父亲节点变为他的父亲。对每个子树也是像这样处理。注意一个是另一个的祖先的情况。代码如下：var father,son:array[0..10001] of longint;//father是返回时的父亲节点编号，原来指向自己，son是该节点的儿子个数 s:array[0..10001,0..101] of longint;//表示一个节点的儿子编号，因为数据比较弱直接开数组，否则要用链表 f:array[0..10001] of boolean; i,j,t,n,get,u,v,x,y:longint;function find(x:longint):longint;begin if father[x]=x then exit(x) else father[x]:=find(father[x]); exit(father[x]);end;//并查集路径压缩，不解释，网上题解比较多的procedure tarjan(x:longint);var i:longint;begin if f[u] and f[v] then exit; f[x]:=true; if (x=u) and f[v] then get:=find(v);//已经找到了两个节点，显然u的父亲节点还没有变动，但是v的已经变动过了，实质上指向的是同一个祖先，所以找v的祖先。下面也是如此 if (x=v) and f[u] then get:=find(u); for i:=1 to son[x] do if not(f[s[x,i]]) then begin tarjan(s[x,i]);//遍历子树 father[s[x,i]]:=x;//没有找到，父亲节点指向它 end;end;begin readln(t); for i:=1 to t do begin readln(n); fillchar(f,sizeof(f),false); fillchar(son,sizeof(f),0); for j:=1 to n do father[j]:=j; for j:=1 to n-1 do begin readln(x,y); inc(son[x]); s[x,son[x]]:=y; father[y]:=x; end; readln(u,v); x:=find(n);//找树根，不解释 for j:=1 to n do father[j]:=j;//父亲节点指向自己 tarjan(x); writeln(get); end;end.总结：算法实质是这样的，首先找到了其中一个节点，然后不断向上，发现一个节点的另一个子树中有另外一个节点，那么这个节点就是他们的lca吐槽一句：你是因为网上的都是c++的然后就强调pascal的吧！好的话记得采纳啊！纯手打很累的！