强连通分量tarjan缩点


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