Posts tagged with Kosaraju


算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一篇博文中提到过,ACM中求强联通分量的常见算法有三种: 暴力 Tarjan Kosaraju 其中暴力和 Kosaraju 算法在求强联通分量的同时,可以直接输出可行解,而Tarjan则需要通过额外的拓扑排序来得出可行解。 简单说一下 Kosaraju 的基本思路: Kosaraju算法主要通过一个非常显然的性质来求强联通分量的。 对于一个强联通分量,将它的所有边反向,那么它依然是一个强联通分量。 因此,我们通过两边dfs,第一遍dfs求出整张图的拓扑序,第二遍dfs按照拓扑序通过反向边进行拓展。…