Using Strongly Connected Component Algo to check if a vertex is reachable

Question

I would like to see if a given vertex, say V0, can be reachable by all other vertices in a graph G.
I know I can just traverse through each vertex in the graph and do BFS/DFS to see if V0 is reachable.
However, this seems to be very inefficient.

I was wondering if i do SCC algo on the graph and if v0 is part of all scc, then I can safely conclude that v0 is reachable by all vertices? This would be great because the cost of SCC is only O(V+E) with Tarjan's and checking to see if v0 is part of scc would also cost linear time.

I would think this makes sense because SCC means vertices are reachable. Any confirmation to this logic?

or any efficient approach to this?

Answer 1

V0 may not belong to SCC, but still be reachable by all other vertices. For example, vertex d on diagram is reachable by all other vertices, but the only non-trivial SCC contains vertices a, b, c and does not contain vertex d.

To check if V0 is reachable by all other vertices, you can reverse direction of every edge (in linear time), then use BFS/DFS, starting from V0, to check if every other vertex is reachable from V0 (also in linear time).

Answer 2

Let us call a vertex from which all other vertices are reachable, a vista vertex. If the graph has a vista vertex, then it must have only one source SCC (since two source SCCs are not reachable from each other), which must contain the vista vertex (if its in any other SCC, there is no path from the vista vertex to the source SCC). Moreover, in this case every vertex in the source SCC will be a vista vertex. The algorithm is then simply to a DFS starting from any node and mark the vertex with the highest finishing time. This must be in a source SCC. We now again run a DFS from this vertex to check if we can reach all nodes. Since the algorithm just uses decomposition into SCCs and DFS, the running time is linear. This algorithm is correct. Note that a vista vertex will exist if and only if there is only one source SCC. Any vertex in a source SCC is only reachable by other vertices in the same SCC, so no vertex can reach vertices in two distinct source SCCs. Furthermore, if there is only one source SCC, any vertex in that SCC is a vista vertex as they are all reachable from each other. Note that a DFS that starts in any particular SCC will not finish until all of the SCCs reachable from it have been explored. This implies that the last node to finish is in a SCC that is not reachable from any other SCCs, i.e. a source SCC. Thus in the first part of our algorithm we find a node in a source SCC. By performing DFS, we will correctly determine whether or not it is a vista vertex, and if it is not a vista vertex, we know that none exist in our graph.