我对这个问题有疑问:
给定包含N个顶点和M个边的有向图,请确定“对于所有 1 <= i, j <= N ,存在从顶点i到顶点j的路径” .
1 <= i, j <= N
我想解决 N <= 500, M <= 250000 .我用dfs找到了天真的寻路算法,但时间复杂度是 O(N^2 M) ,所以它非常慢 .请告诉我解决它的有效算法 .
N <= 500, M <= 250000
O(N^2 M)
例如,如果给出了这个图:
答案是否定的,因为没有从4到1的路径 .
我可以用 O(N+M) 复杂度实现以下算法 .
O(N+M)
取任何顶点 u . 使用flood fill算法到达其他顶点 . 如果无法访问任何顶点,请返回 NOK .
u
NOK
现在也这样做,但转向相反的方向 . 如果无法访问任何顶点,请返回 NOK .
返回 OK . (这里我们知道由于[2],从任何顶点 v 到 u 都有一条路径,并且由于[1],从 u 到任何顶点 w 都有一条路径 . )
OK
v
w
1 回答
我可以用
O(N+M)
复杂度实现以下算法 .取任何顶点
u
. 使用flood fill算法到达其他顶点 . 如果无法访问任何顶点,请返回NOK
.现在也这样做,但转向相反的方向 . 如果无法访问任何顶点,请返回
NOK
.返回
OK
. (这里我们知道由于[2],从任何顶点v
到u
都有一条路径,并且由于[1],从u
到任何顶点w
都有一条路径 . )