郁郁青青 长过千寻

强连通分量tarjan缩点

    图论

  1. MAIN()
  2. TARJAN(U)

MAIN()

1
2
3
4
5
6
7
cnt:=1
res:=0
for i=1 to 总点数
if book[i]=0
TARJAN(i) endif
endfor
print res

TARJAN(U)

1
2
3
4
5
6
7
8
9
10
11
12
book[u]:=1
low[u]:=dfn[u]:=cnt
cnt:=cnt+1
for i:=0 to (连接u的点数-1)
v:=连接u的第(i+1)个点
if book[v]=0
TARJAN(v) endif
if book[v]=1
low[u]=MIN(low[u],low[v]) endif
endfor
if dfn[u]=low[u]
res:=res+1
页阅读量:  ・  站访问量:  ・  站访客数: