Kosaraju算法入门 ( 附 POJ 2186
算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一篇博文中提到过，ACM中求强联通分量的常见算法有三种： 1. 暴力 2. Tarjan 3. Kosaraju 其中暴力和 Kosaraju 算法在求强联通分量的同时，可以直接输出可行解，而Tarjan则需要通过额外的拓扑排序来得出可行解。 简单说一下 Kosaraju 的基本思路： Kosaraju算法主要通过一个非常显然的性质来求强联通分量的。 对于一个强联通分量，将它的所有边反向，那么它依然是一个强联通分量。 因此，我们通过两边dfs，第一遍dfs求出整张图的拓扑序，第二遍dfs按照拓扑序通过反向边进行拓展。 这个地方就非常巧妙。因为在按照拓扑序遍历的过程中，对于一个点，如果它是一个强联通分量的一个点，那么除开原先遍历标记过点，必然会存在拓扑序在该点之后但仍然指向该点的一个点。 好难表达，yy很容易 题解 题意： 有一群牛，给你很多个关系，一对关系 a -> b 表示 a 认为 b 是肥宅，问被所有牛公认为肥宅的牛有几头。…