强连通分量 – 缩点
这篇文章咕了两个月。感谢 @rickyxrc 的催更。 如果你还不知道什么是强连通分量的话,参见我本系列的上一篇文章:强连通分量 – Kosaraju Algorithm 引入 强连通分量的缩点,就是把图上的每一个强连通分量都视作一个点(或者更通俗的,缩成一个点)。SCC 与 SCC 之间的边连接依然参照原图保留。 缩点解决了部分算法「跑不了环」的问题,比如拓扑排序。并且对于部分题目,缩点之后的图对于原图来说没有太大的区别。 图示 如图所示,1 2 3 和 4 5 6 分别属于两个 SCC。把 […]