Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e. every vertex is reachable from every other vertex.
what's a good algorithm to check for this that runs in O(m) time? (the number of edges) where we assume that n < m. (there are always more edges than vertices in the graph)
As mentioned by others, we can assume $n \le m$ otherwise the answer is NO. Perform a visit (say, a DFS) from node 1 along the digraph; and then, a visit from node 1 along the "reverse" digraph in which all the edges are reversed (after precomputing the reverse digraph in linear time). If both visits hit all nodes of the digraph, it is strongly connected. If not, it can't be.
The algorithms on the Wikipedia page linked by @idmean indeed run in $O(n + m)$ time, but this is only because they don't just test if a graph is strongly connected, but also find each strongly connected component. However, if we only want to test if the entire graph is strongly connected, such an algorithm can run in $O(m)$ time. The key observation is that if $m < n$, we know the graph is not strongly connected: there simply aren't enough edges to do the job! Therefore, we can assume that $n \in O(m)$, and therefore the running time simplifies to $O(m)$ time.
Find the number of SCC of input graph $G$ in $\mathcal{O}(n+m)$, then check whether the number SCC is $1$ or not. If the number of SCC is $1$ then $G$ is strongly connected. Note that, according your observation $n<m$ we can conclude that $\mathcal{O}(n+m)=\mathcal{O}(m).$
One efficient algorithm to check if a directed graph is strongly connected is Kosaraju's algorithm. It runs in O(m) time complexity, where m is the number of edges in the graph. This algorithm involves two depth-first searches (DFS) and can determine if every vertex is reachable from every other vertex.
