Tarjan算法

应用:

• 有向图的强连通分量
• 无向图割点和桥
• 双连通分量

接下来主要谈论前面两者的应用(主要是第三种还没学会)

算法简要介绍

我们需要先理解一下知识:搜索树

• 有向图的搜索树的4种边，如下图所示:
  

tree edge:在dfs搜索u的过程中，第一次搜索v，则(u,v)是树边

forward edge: u是v在树中祖先, 在dfs(u)的过程中v已经被访问过

back edge: u是v在树中后裔, 在dfs(u)的过程中v已经被访问过

cross edge: 若u和v没有祖先-后裔（后裔-祖先）关系，且在explore(u)前v已经被访问过

未完待续