c++ - 确定有向图上所有顶点对之间是否存在路径

Question

问题

我有一个关于这个问题的问题：

给定一个包含 N 个顶点和 M 个边的有向图，请确定“所有的顶点 i 到顶点 j 都有一条路径1 <= i, j <= N”。

我想解决N <= 500, M <= 250000.
我用 dfs 找到了简单的寻路算法，但时间复杂度是O(N^2 M)，所以速度很慢。
请告诉我解决它的有效算法。

例子

例如，如果给出此图：

答案是否定的，因为没有从 4 到 1 的路径。

Answer 1

以下算法可以O(N+M)复杂地实现。

1. 取任意顶点u。使用洪水填充算法到达其他顶点。如果任何顶点不可到达，则返回NOK。

2. 现在做同样的事情，但往相反的方向走。如果任何顶点不可到达，则返回NOK。

3. 返回OK。（这里我们知道，由于[2]，存在从任意顶点v到的路径，由于[1]，存在从任意顶点到任意顶点的路径。）uuw