Tarjan

DFN[u]:u被搜索的次序编号

LOW[u]:u的子树中最小编号

有向图:当DFN(u)=LOW(u)时,以u为根的树上所有点是一个强连通分量

无向图:当LOW[v]>DNF[u]时(u,v)为桥

 

Tarjan缩点代码:

 

Tarjan求桥代码:

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz