Tarjan算法详解

效率确实是太低了，居然学习这个算法也用了我一个下午，很大的原因应该是没有找到好的课件或者说理解能力有待提高吧！

说实话，其实tarjan算法也比较简单，下面大概说说tarjan算法吧：

【功能】

    Tarjan算法的用途之一是，求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话，那么这个强连通分量就是极大强连通分量。

【算法思想】

    用dfs遍历G中的每个顶点，通dfn[i]表示dfs时达到顶点i的时间，low[i]表示i所能直接或间接达到时间最小的顶点。(实际操作中low[i]不一定最小，但不会影响程序的最终结果)

    程序开始时，time初始化为0，在dfs遍历到v时，low[v]=dfn[v]=time++，

v入栈（这里的栈不是dfs的递归时系统弄出来的栈）扫描一遍v所能直接达到的顶点k，如果 k没有被访问过那么先dfs遍历k，low[v]=min(low[v],low[k])；如果k在栈里，那么low[v]=min(low[v],dfn[k])(就是这里使得low[v]不一定最小，但不会影响到这里的low[v]会小于dfn[v])。扫描完所有的k以后，如果low[v]=dfn[v]时，栈里v以及v以上的顶点全部出栈，且刚刚出栈的就是一个极大强连通分量。

【大概的证明】

 1．  在栈里，当dfs遍历到v，而且已经遍历完v所能直接到达的顶点时，low[v]=dfn[v]时，v一定能到达栈里v上面的顶点：

    因为当dfs遍历到v，而且已经dfs递归调用完v所能直接到达的顶点时（假设上面没有low=dfn），这时如果发现low[v]=dfn[v]，栈上面的顶点一定是刚才从顶点v递归调用时进栈的，所以v一定能够到达那些顶点。

 

2 .dfs遍历时，如果已经遍历完v所能直接到达的顶点而low[v]=dfn[v]，我们知道v一定能到达栈里v上面的顶点，这些顶点的low一定小于 自己的dfn，不然就会出栈了，也不会小于dfn[v],不然low [v]一定小于dfn[v],所以栈里v以其v以上的顶点组成的子图是一个强连通分量，如果它不是极大强连通分量的话low[v]也一定小于dfn[v]（这里不再详细说），所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量。

【时间复杂度】

     因为所有的点都刚好进过一次栈，所有的边都访问的过一次，所以时间复杂度为O（n+m）

 

【参考代码（pascal）】

  type

  emap=record   //边表

    v1,v2,next:longint;

  end;

  vmap=record  //first表示顶点v的第一条边在边表的位置，last表示最后一条边的位置

    first,last:longint;

  end;

var

  e:Array[1..10000] of emap;

  a:array[1..100] of vmap;

  dfn,low:array[1..100] of longint;

  i,j,n,m,v1,v2,ei,zi,time:longint;   //zi表示栈中元素的数量，time表示dfs的时间

  zhan:Array[1..1000] of longint;  //栈堆

  visit:array[1..100] of boolean;  //true表示有被dfs遍历过

  zvisit:array[1..100] of longint; //表示顶点v在栈中的什么位置

function min(a,b:longint):longint;

begin

  if a<b then exit(a) else exit(b);

end;

procedure push(v:longint);  //把v进栈

begin

  inc(zi);

  zvisit[v]:=zi;

  zhan[zi]:=v;

end;

procedure chuzhan(v:longint);    //把v以及v以上的全部出栈

var

  lin:longint;

begin

  lin:=zvisit[v];

  for i:=lin to zi do

  begin

    if i=zi then writeln(zhan[i])

    else write(zhan[i],' ');

    zvisit[zhan[i]]:=0;

  end;

  zi:=lin-1;

end;

procedure dfs(v:longint);

var

  i,j,zhi,k:longint;

begin

  inc(time);

  dfn[v]:=time; low[v]:=time;

  zhi:=a[v].first;

  visit[v]:=true;

  push(v);

  while zhi<>-1 do

  begin

    k:=e[zhi].v2;

    if not visit[k]  then    //如果k没有被访问过

    begin

      dfs(k);     //dfs遍历k

      low[v]:=min(low[v],low[k]); 

    end else

    if  (zvisit[k]>0) then    //如果k在栈里

    low[v]:=min(low[v],dfn[k]);

    zhi:=e[zhi].next;

  end;

  if low[v]=dfn[v] then

    chuzhan(v);      //把v及以上的顶点出栈并输出

end;

begin

  readln(n,m);   //读入顶点数和边数

  for i:=1 to n do a[i].first:=-1;

  ei:=0;

  for i:=1 to m do    //读入边，并把它保存到特殊边表里

  begin

    readln(v1,v2);

    if a[v1].first=-1 then

    begin

      inc(ei);

      e[ei].v1:=v1; e[ei].v2:=v2;

      e[ei].next:=-1;

      a[v1].first:=ei; a[v1].last:=ei;

    end else

    begin

      inc(ei);

      e[ei].v1:=v1; e[ei].v2:=v2;

      e[ei].next:=-1;

      e[a[v1].last].next:=ei;

      a[v1].last:=ei;

    end;

  end;

  fillchar(visit,sizeof(visit),false);     //初始化全部都没有被访问过

  fillchar(zvisit,sizeof(zvisit),0);     //初始化全部都不在栈里

  time:=0;  zi:=0;   //初始化时间为0，栈为空

  for i:=1 to n do  //预防顶点1不能到达所有的点

  begin

    if not visit[i] then

    dfs(i);

  end;

end.

以上代码纯属照写，经优化后的核心代码：

function getfather(dep:longint):longint;

begin

  if father[dep]=dep then exit(dep);

  getfather:=getfather(father[dep]);

  father[dep]:=getfather;

end;

procedure dfs(dep:longint);

var

  i,j,v2:longint;

begin

  inc(time);

  low[dep]:=time;

  check[dep]:=true; zhan[dep]:=true;

  for i:=1 to n do

  begin

    if map[dep,i]=1 then

    begin

      if not check[i] then dfs(i);

       v2:=getfather(i);

      if zhan[v2] then

      if low[v2]<low[dep] then begin

        low[dep]:=low[v2];

        father[dep]:=v2;

      end;

    end;

  end;

  zhan[dep]:=false;

end;