Efficient algorithm to find vertex with paths to every other vertex
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.