如何求一个有向图的强连通分量数目子图有多少种 tarjan算法

一次找到一个强连通分量内的所囿点

该算法充分利用了深度优先搜索的顺序性 以及 对以及确保处理完的强连通分量不会干扰后面求强连通分量的过程

记(xy)为 从x 到 y 的一條边

记dfn为深度优先遍历的时间戳

时间戳就是dfs到这个点的次序

记low(u) 为时间戳为u的点所能到达的在栈内最小时间戳的点


 
 
 
 

建议把下面的图自己跑一遍//中括号是low

我要回帖

更多关于 有向图的强连通分量数目 的文章

 

随机推荐