Directed graph connectivity

Given a directed graph G, what is the best way to go about finding a vertex v such that there is a path from v to every other 开发者_StackOverflow中文版vertex in G?

This algorithm should run in linear time. Is there an existing algorithm that solves this? If not, I'd appreciate some insight into how this can be solved in linear time (I can only think of solutions that would certainly not take linear time).

Make a list L of all vertices.

Choose one; call it V. From V, walk the graph, removing points from the list as you go, and keeping a stack of unvisited edges. When you find a loop (some vertex you visit is not on the list), pop one of the edges from the stack and proceed.

If the stack is empty, and L is not empty, then choose a new vertex from L, call it V, and proceed as before.

When L is finally empty, the V you last chose is an answer.

This can be done in linear time in the number of edges.

1. Find the strongly connected components.
2. Condense each of the components into a single node.
3. Do a topological sort on the condensed graph, The node with the highest rank will have a path to each of the other nodes (if the graph is connected at all).

I think I've got a correct answer.

1. Get the SCC.
2. Condense each of the components into a single node.
3. Check whether every pair of adjacent nodes is reachable.

This is a sufficient and necessary condition.