首先还是说明这是一个坑

 

然后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]
      
       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
      

 

无向图模版（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]