0
$\begingroup$

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)

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

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.

$\endgroup$
0
$\begingroup$

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).$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.