[Solved]: Efficient algorithm to find vertex with paths to every other vertex

Problem Detail: 

$G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other vertex), or "false" if there aren't any. If there are more than one, return one of them.

The obvious and inefficient way would be to run BFS from every vertex, checking after every run of BFS if there are vertices with distance $= \infty$. If not - that vertex has paths to every other vertex. Complexity would be $O(|E||V| + |V|^{2})$.

I can't think of any substantial improvements. If someone could point me in the right direction (pun intended), that would be great!

Asked By : Cauthon

Answered By : Tom van der Zanden

You'll need to split the graph in to its strongly connected components, and then find a component from which you can reach every other component.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35803