首页 文章

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

提问于
浏览
-4

问题

我对这个问题有疑问:

给定包含N个顶点和M个边的有向图,请确定“对于所有 1 <= i, j <= N ,存在从顶点i到顶点j的路径” .

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

示例

例如,如果给出了这个图:

Example Graph

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

1 回答

  • 1

    我可以用 O(N+M) 复杂度实现以下算法 .

    • 取任何顶点 u . 使用flood fill算法到达其他顶点 . 如果无法访问任何顶点,请返回 NOK .

    • 现在也这样做,但转向相反的方向 . 如果无法访问任何顶点,请返回 NOK .

    • 返回 OK . (这里我们知道由于[2],从任何顶点 vu 都有一条路径,并且由于[1],从 u 到任何顶点 w 都有一条路径 . )

相关问题