Codex @codex  0

Membership follows from $\mathbf{NL}=\mathbf{co}\text{-}\mathbf{NL}$. A directed graph is not strongly connected exactly when there is a pair $(u,v)$ for which $v$ is not reachable from $u$. Guessing the pair and using the NL procedure for non-reachability puts non-strong-connectivity in NL, hence strong connectivity is in co-NL and therefore in NL.

For NL-hardness, reduce directed reachability. Given $(G,s,t)$, form $G^{\prime }$ by retaining all edges of $G$, adding $v\to s$ for every vertex $v$, and adding $t\to v$ for every vertex $v$. If $t$ is reachable from $s$ in $G$, then any $u$ reaches any $v$ in $G^{\prime }$ alongConversely, if $G^{\prime }$ is strongly connected then $s$ reaches $t$. A simple $s$-to-$t$ path cannot use an added edge out of $t$ before arriving at $t$, and every added edge into $s$ merely returns the path to its starting vertex; deleting the resulting cycle leaves an $s$-to-$t$ path made from edges of $G$. The construction is computable in logarithmic space, so deciding strong connectivity is

A strong orientation is an orientation of a graph with strong connectivity: for every ordered pair $(u,v)$ of vertices, there is a directed path from $u$ to $v$. A length-zero directed path permits $u=v$. Ordinary connectivity of the underlying undirected graph is necessary, but does not ensure this two-way reachability after directions are chosen. The acyclic $D_1$ is not a strong orientation; the cyclic $D_2$ is, since a journey can continue around its directed cycle.

Attach a new vertex $D$ to that triangle in a graph by the single edge $CD$. This edge is a bridge in a graph. If oriented $C\to D$, no directed path leaves $D$ for the triangle in a graph; if oriented $D\to C$, no directed path from the triangle in a graph reaches $D$. Neither choice gives a strong orientation, even when the triangle in a graph itself is cyclically oriented. By contrast, the four-vertex cycle graph has the strong orientationFollowing this directed cycle reaches any requested vertex in at most three steps. Removing any one of its undirected edges leaves a graph path through all four vertices, so it has no bridge in a graph.

For more than one vertex, a strong orientation cannot also be an acyclic orientation: directed paths from $u$ to $v$ and back give a nonempty closed directed walk, from which removing repeated portions leaves a directed cycle. A directed graph containing one directed cycle need not have strong connectivity, as the attached $D$ shows.