$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!
Efficient algorithm to find vertex with paths to every other vertex
algorithms;graphs;search algorithms
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.