# O(m) time algorithm to check for a strongly connected graph

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)

• Wikipedia has list of well-known algorithms for this: en.wikipedia.org/wiki/Strongly_connected_component Aug 16, 2021 at 16:20
• @idmean don't these algorithms run in O(n+m) time?
– user141218
Aug 16, 2021 at 16:22
• If you have $n < m$ then $n+m<m+m=2m \in O(m)$. Aug 16, 2021 at 16:23

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 we can conclude that $$\mathcal{O}(n+m)=\mathcal{O}(m).$$