首页 > 代码库 > tarjan
tarjan
首先还是说明这是一个坑
然后tarjan以前一直处于懵懵懂懂的状态，决定痛改前非好好学。
tarjan可以用来求强联通分离。
它有两个数组，一个是dfn，一个是low。
定义DFN（u）为节点u搜索的次序编号（时间戳）。Low（u）为u或者u的子树能够追溯到的最早的栈中的节点的次序号。
然后就发现u的儿子无非三种情况：一是还没访问过，然后是访问过而且已经在某个强联通分量里面，最好是访问过但是还在栈里面。
对于第一种情况就直接访问
然后low[u]=min(low[u],low[son])
对于第二种情况无视
对于第三种情况low[u]=min(low[u],dfn[son]);
然后可以发现一些东西
对于有向图，low[x]=dfn[x]则x为强联通分量的开始
对于无向图，如果low[x]<=dfn[x]那么x为割点，如果low[v]<dfn[x]那么边(x,v)为割边（桥）
然后才现在原来我的tarjan和别人不一样，我对于第三种情况low的维护和第一种情况一样！但是yy了下好像是可以……求路过大神推翻……
有向图模版（直接拿bzoj1179: [Apio2009]Atm，题解后空再写（反正是水题反正写了也没人看））
type arr=record next,toward:longint; end;const maxm=1000000; maxn=600000; mm=600000;var edge:array[0..maxm]of arr; f1,f2,value,num,scc,p,dfn,low,d:array[0..maxn]of longint; chose:array[0..maxn]of boolean; n,m,tot,tail,ss,time,sum:longint; procedure add1(j,k:longint);begin inc(tot); edge[tot].toward:=k; edge[tot].next:=f1[j]; f1[j]:=tot;end; procedure add2(j,k:longint);begin inc(tot); edge[tot].toward:=k; edge[tot].next:=f2[j]; f2[j]:=tot;end; procedure tarjan(x:longint);var i,too,j:longint;begin inc(time); dfn[x]:=time; low[x]:=time; chose[x]:=true; inc(tail); p[tail]:=x; i:=f1[x]; while i>0 do begin too:=edge[i].toward; if dfn[too]=0 then begin tarjan(too); if low[too]<low[x] then low[x]:=low[too]; end else if chose[too] and (dfn[too]<low[x]) then low[x]:=dfn[too]; i:=edge[i].next; end; if low[x]=dfn[x] then begin inc(sum); num[sum]:=0; repeat j:=p[tail]; dec(tail); chose[j]:=false; scc[j]:=sum; num[sum]:=value[j]+num[sum]; until j=x; end;end; procedure spfa;var head,tail,x,i,too:longint;begin tail:=1; head:=0; fillchar(d,sizeof(d),0); fillchar(chose,sizeof(chose),false); p[1]:=scc[ss]; d[p[1]]:=num[p[1]]; chose[p[1]]:=true; while head<>tail do begin inc(head); if head>mm then head:=1; x:=p[head]; i:=f2[x]; // writeln(x); while i>0 do begin too:=edge[i].toward; if d[x]+num[too]>d[too] then begin d[too]:=d[x]+num[too]; if not chose[too] then begin inc(tail); if tail>mm then tail:=1; p[tail]:=too; chose[too]:=true; end; end; i:=edge[i].next; end; chose[x]:=false; end;end; procedure into;var i,j,k,x,too:longint;begin read(n,m); tot:=0; for i:=1 to m do begin read(j,k); add1(j,k); end; for i:=1 to n do read(value[i]); for i:=1 to n do if dfn[i]=0 then tarjan(i); for x:=1 to n do begin i:=f1[x]; while i>0 do begin too:=edge[i].toward; if scc[too]<>scc[x] then add2(scc[x],scc[too]); i:=edge[i].next; end; end;end; procedure work;var ans,i,j,total:longint;begin read(ss,total); spfa; ans:=0; for i:=1 to total do begin read(j); if ans<d[scc[j]] then ans:=d[scc[j]]; end; writeln(ans);end; begin into; work;end.
无向图模版（bzoj1123: [POI2008]BLO）
type arr=record toward,next:longint; end;const maxn=300000; var edge:array[0..maxn*5]of arr; dfn,low,first,size:array[0..maxn]of longint; sum:array[0..maxn]of int64; n,m,time,tot,i:longint; procedure addedge(j,k:longint);begin inc(tot); edge[tot].toward:=k; edge[tot].next:=first[j]; first[j]:=tot;end; procedure tarjan(x:longint);var i,too,son:longint;begin inc(time); dfn[x]:=time; low[x]:=time; son:=0; size[x]:=1; i:=first[x]; while i>0 do begin too:=edge[i].toward; if dfn[too]=0 then begin tarjan(too); size[x]:=size[x]+size[too]; if low[too]<low[x] then low[x]:=low[too]; if dfn[x]<=low[too] then begin sum[x]:=sum[x]+int64(son)*size[too]; son:=son+size[too]; end; end else if dfn[too]<low[x] then low[x]:=dfn[too]; i:=edge[i].next; end; sum[x]:=sum[x]+int64(son)*(n-son-1);end; procedure into;var i,j,k:longint;begin read(n,m); tot:=0; for i:=1 to m do begin read(j,k); addedge(j,k); addedge(k,j); end; tarjan(1);end; begin into; for i:=1 to n do writeln((sum[i]+n-1)<<1);end.
tarjan
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。