[Solved] Determine if there is a path between all vertex pairs on an directed graph

by


The following algorithm can me implemented with O(N+M) complexity.

  1. Take any vertex u. Use flood fill algorithm to reach other vertices. If any vertex is not reachable, return NOK.

  2. Now do the same, but go to the opposite direction. If any vertex is not reachable, return NOK.

  3. Return OK. (Here we know that there is a path from any vertex v to u because of [2], and there is a path from u to any vertex w because of [1].)

solved Determine if there is a path between all vertex pairs on an directed graph