确定有向图上所有顶点对之间是否存在路径
Determine if there is a path between all vertex pairs on an directed graph
问题
我对这个问题有疑问：
给定一个包含N个顶点和M条边的有向图，请确定"there is a path from vertex i to vertex j for all 1 <= i, j <= N"。
我想解决 N <= 500, M <= 250000。
我用 dfs 找到了朴素的寻路算法，但是时间复杂度是 O(N^2 M)，所以它很慢。
请告诉我解决它的有效算法。
例子
例如，如果给定此图：
答案是否定的，因为没有从 4 到 1 的路径。
我可以用 O(N+M) 复杂度实现以下算法。
取任意顶点u。使用flood fill算法到达其他顶点。如果任何顶点不可到达，return NOK.
现在做同样的事情，但是往相反的方向走。如果任何顶点不可到达，return NOK.
ReturnOK。 （这里我们知道有一条从任意顶点v到u的路径，因为[2]，并且有一条从u到任意顶点w的路径，因为[1].)
问题
我对这个问题有疑问：
给定一个包含N个顶点和M条边的有向图，请确定"there is a path from vertex i to vertex j for all 1 <= i, j <= N"。
我想解决 N <= 500, M <= 250000。
我用 dfs 找到了朴素的寻路算法，但是时间复杂度是 O(N^2 M)，所以它很慢。
请告诉我解决它的有效算法。
例子
例如，如果给定此图：
答案是否定的，因为没有从 4 到 1 的路径。
我可以用 O(N+M) 复杂度实现以下算法。
取任意顶点
u。使用flood fill算法到达其他顶点。如果任何顶点不可到达，returnNOK.现在做同样的事情，但是往相反的方向走。如果任何顶点不可到达，return
NOK.Return
OK。 （这里我们知道有一条从任意顶点v到u的路径，因为[2]，并且有一条从u到任意顶点w的路径，因为[1].)