首页 > 代码库 > tarjan算法模板

tarjan算法模板

var{left表示点 root 没离开栈 vis表示点 root 有没有被访问过}  i,n,m,now,time,color,top:longint;  v:array[0..10001] of record start:longint;end;  e:array[0..100001] of record y,next:longint;end;  dfn,low,stack,encolor:array[0..10001] of longint;  vis,left:array[0..10001] of boolean;procedure indata;  var i,xx,yy,op:longint;  begin    time:=0;  color:=0;  top:=0;    fillchar(e,sizeof(e),0);    fillchar(v,sizeof(v),0);    fillchar(dfn,sizeof(dfn),0);    fillchar(low,sizeof(low),0);    fillchar(vis,sizeof(vis),0);    fillchar(left,sizeof(left),1);    fillchar(encolor,sizeof(encolor),0);  end;procedure tarjan(root:longint);  var te,tv,ttimes:longint;  begin    inc(time);    dfn[root]:=time;  low[root]:=time;    inc(top);  stack[top]:=root;    {点 root 入栈 }    left[root]:=false; vis[root]:=true;    te:=v[root].start;    while (te<>0) do      begin        tv:=e[te].y;        if not left[tv] then          low[root]:=min(low[root],dfn[tv]);        if not vis[tv] then          begin            tarjan(tv);            low[root]:=min(low[root],low[tv]);          end;        te:=e[te].next;      end;    if (dfn[root]=low[root]) then      begin        inc(color);   tv:=0;        while (tv<>root) do          begin            tv:=stack[top];            dec(top);            encolor[tv]:=color;            left[tv]:=true;          end;      end;  end;