无向图双连通分量的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>

评论

0条评论

发表回复

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

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