首页 > 代码库 > 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;
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。