在看提高课强连通分量的视频的时候,在想为什么拓扑排序的顺序是强联通分量的编号倒序,思想一番后得到以下结果,如有错误,请dalao们指出。
在tarjan求强连通分量中,其强连通分量的编号顺序是根据缩点后得到的拓扑排序从最后一个点到第一个点来排序的,因为在tarjan过程中,是在利用dfs进行遍历点,我们知道dfs在一棵树当中,是会遍历到最后一个叶结点,然后再回溯到其上面的根结点,所以是会先得到位于拓扑排序中的最后一个强连通分量,因此,在递推拓扑排序的时候需要从编号由大到小开始。
从最后一个点到第一个点