有向图强连通分量的tarjan算法摸板

  • 内容
  • 评论
  • 相关

其实我在不久之前还以为有向图的强连通分量算法是和无向图的双联通分量算法是一样的呢。。。打的时候发现有点不对劲,的确有向图强连通分量的tarjan是要稍微麻烦一点的。。。


代码:

var
  a,next,v,low,dfn,st,be:array[0..5000000]of longint;
  b:array[0..5000000]of boolean;
  n,m,i,j,k,p,q:longint;
procedure adde(uu,vv:longint);
begin
  inc(k);
  v[k]:=vv;
  next[k]:=a[uu];
  a[uu]:=k;
end;
procedure dfs(n:longint);
var
  i:longint;
begin
  inc(k);
  dfn[n]:=k;
  low[n]:=k;
  b[n]:=true;
  inc(st[0]);
  st[st[0]]:=n;
  i:=a[n];
  while i<>0 do
  begin
    if dfn[v[i]]=0 then
    begin
      dfs(v[i]);
      if low[v[i]]<low[n] then low[n]:=low[v[i]];
    end
    else if b[v[i]] and (dfn[v[i]]<low[n]) then low[n]:=dfn[v[i]];
    i:=next[i];
  end;
  if dfn[n]=low[n] then
  begin
    inc(t);
    repeat
      be[st[st[0]]]:=t;
      b[st[st[0]]]:=false;
      dec(st[0]);
    until st[st[0]+1]=n;
  end;
end;
procedure adde2(uu,vv:longint);
begin
  inc(k);
  v2[k]:=vv;
  next2[k]:=a2[uu];
  a2[uu]:=k;
end;
begin
  read(n,m);
  for i:=1 to m do
  begin
    read(p,q);
    adde(p,q);
  end;
  k:=0;
  fillchar(b,sizeof(b),false);
  for i:=1 to n do if be[i]=0 then
  dfs(i);//be[i]表示i属于的强连通分量的编号
end.

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据