Using Strongly Connected Component Algo to check if a vertex is reachable
algorithm, graph
Solution
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).
Problem
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?