无向图双连通分量的tarjan算法模板
之前做了一些tarjan题目,总结一下模板。
其实没啥好说的,上代码:
var v,next:array[1..300000]of longint; low,dfn,a:array[0..100000]of longint; b:array[0..100000]of boolean; n,m,i,j,k,p,q,x,y:longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure dfs(u,p:longint); var i:longint; begin b[u]:=true; inc(k); dfn[u]:=k; low[u]:=k; i:=a[u]; while i<>0 do begin if not b[v[i]] then begin dfs(v[i],u); low[u]:=min(low[u],low[v[i]]); end; if b[v[i]] and (v[i]<>p) then low[u]:=min(low[u],dfn[v[i]]); i:=next[i]; end; end; procedure adde(uu,vv:longint); var i:longint; begin i:=a[uu]; while i<>0 do begin if v[i]=vv then exit; i:=next[i]; end; inc(k); v[k]:=vv; next[k]:=a[uu]; a[uu]:=k; inc(k); v[k]:=uu; next[k]:=a[vv]; a[vv]:=k; end; begin read(n,m); k:=0; for i:=1 to m do begin read(x,y); adde(x,y); end; fillchar(b,sizeof(b),false); k:=0; dfs(1,1); end.</b>
发表回复