Tarjan算法的相关应用

强连通分量

定义略。

用Tarjan算法来求解强连通分量,在此之前,先明确这两个定义:

  • 返祖边:由一个点指向其祖先的边。

  • 横插边: 由一个节点指向非祖先节点的边。(只有有向图会出现)

这两种边都是dfs树的非树边。

定义这两个数组:

  • dfndfn: dfs序。

  • lowlow: 不经横插边所能到达的点中最小的dfndfn

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×