# Efficient algorithm to find vertex with paths to every other vertex

$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!

• Won't that still leave me with $O(|E||V| + |V|^{2})$? Since we don't know how many SCCs there are, they might be in the same order of the number of vertices (if they're very small SCCs). So wouldn't I still have to run a (modified) BFS from every SCC (the same as doing it from every vertex)? – Cauthon Dec 31 '14 at 23:45
• I don't see how to do it under linear time for each and every component. Let's say there are $|V|/3$ strongly connected components. I can start from one of them, and continue to the next, but if every component has only one edge to the next component, I would have to traverse $|V|/3$, doing this for every component. Obviously if it's that easy I'm missing something simple... – Cauthon Jan 1 '15 at 10:34