A directed graph is strongly connected if for all vertices $u$ and $v$ in the graph, there is a directed path from $u$ to $v$. We define the problem $\text{STRONGLY-CONNECTED}$ to be: Given a directed graph $G$, is $G$ strongly connected?
Theorem. $\text{STRONGLY-CONNECTED}$ is $\mathbf{NL}$-complete.
Proof. First, we need to show that this is in $\mathbf{NL}$. We simply go through every pair of vertices $(u,v)$ and run a $\mathrm{PATH}$ algorithm on them. Then we can accept if every pair of vertices accepts and reject if there's a pair that doesn't have a path. This can pretty clearly be done nondeterministically in $O(\log n)$ space.
Now, to show $\mathbf{NL}$-hardness, we will reduce $\mathrm{PATH}$ to $\text{STRONGLY-CONNECTED}$. For a directed graph $G = (V,E)$ and vertices $s$ and $t$, we construct a directed graph $G'$ that has the same vertex set $V$ and a new edge set $E'$, $$ E' = E \cup \{(v,s) \mid v \in V \} \cup \{(t,v) \mid v \in V\}$$ which consists of all edges in $G$ and a new edge from each vertex of $G$ to $s$ and a new edge from $t$ to each vertex of $G$. This function is logspace computable, since the only thing we add are the new edges, which can easily be computed in logarithmic space.
Suppose that there is a directed path from $s$ to $t$ in $G$. Then for every pair of vertices $u$ and $v$, there is a directed path: follow the edge from $u$ to $s$, then traverse the path to $t$ then follow the edge to $v$.
Now, suppose that $G'$ is strongly connected. This means there is a directed path from $s$ to $t$ in $G'$. However, we observe that the only edges we added in $G$ are incoming edges to $s$ and outgoing edges from $t$. In other words, no directed path from $s$ or to $t$ could have been created. Thus, there was a path from $s$ to $t$ in the original graph. $$\tag*{$\Box$}$$
We define $\mathrm{CYCLE}$ to be: Given a directed graph $G$, does $G$ contain a directed cycle?.
Theorem. $\text{CYCLE}$ is $\mathbf{NL}$-complete.
Proof. To see that $\mathrm{CYCLE}$ is in $\mathbf{NL}$, we show that to check for a cycle in a graph $G$, we simply test for each pair of vertices $u$ and $v$ whether there is a path from $u$ to $v$ and a path from $v$ to $u$. If at least one of these pairs is successful, there is a cycle and we can accept. If none of the pairs satisfy this property, then we reject. Since testing paths can be done nondeterministically in $O(\log n)$ space, this algorithm is clearly in $\mathbf{NL}$.
To show hardness, we will show that we can reduce $\mathrm{PATH}$ to $\mathrm{CYCLE}$. Given a graph $G$ and vertices $s$ and $t$, we construct a graph $G'$ that will contain a cycle if and only if $G$ has a path from $s$ to $t$.
If $G = (V,E)$ has $n$ vertices, we construct $G'$ with $n$ copies of $V$ partitioned into subsets called levels $V_1', \dots, V_n'$. For each $i$, we draw an edge from $u \in V_i$ to $v \in V_{i+1}$ if $(u,v)$ is an edge in $G$. We also draw an edge from $u \in V_i$ to $u \in V_{i+1}$.
Let $s'$ be the vertex $s \in V_1$ and $t'$ be the vertex $t \in V_n$. We claim $G$ contains a path from $s$ to $t$ iff $G'$ contains a path from $s'$ to $t'$. Note that $G'$ is still acyclic. So, finally, we add an edge $t'$ to $s'$ and now $G$ contains a path from $s$ to $t$ iff $G'$ contains a cycle. $$\tag*{$\Box$}$$
The bonus question in Assignment 3 asked you to show that this is in $\mathbf P$. As it turns out, we can show something a bit stronger: that $\text{2SAT}$ is in fact $\mathbf{NL}$-complete.
Theorem. $\text{2SAT}$ is $\mathbf{NL}$-complete.
Proof. As it turns out, the graph construction in the solution of Problem 6 of Assignment 3 is computable in logarithmic space: simply output each literal as a vertex and output the edges $(\overline a,b)$ and $(\overline b,a)$ for each clause $(a \vee b)$. Now, recall that our formula is satisfiable iff there is no path from $x$ to $\overline x$ and from $\overline x$ to $x$ for every variable $x$. But, we know that we can test for paths in logarithmic space. Thus, $\mathrm{2SAT} \in \mathbf{NL}$.
Now, we just need to show $\mathbf{NL}$-hardness. To do this, we reduce $\mathrm{\overline{PATH}}$ to $\mathrm{2SAT}$. For a directed graph $G$, we construct a formula $\varphi_G$ such that $\varphi_G$ is satisfiable if and only if there is no path from $s$ to $t$ in $G$.
To construct $\varphi_G$, we map each vertex $v$ of $G$ to a literal in $\varphi_G$. Then for each edge $(u,v)$ in $G$, we add the clause $(\overline u \vee v)$ to $\varphi_G$. Finally, for $s$ and $t$, we add the clauses $(s)$ and $(\overline t)$ (technically these are not 2-clauses, but we learned how to deal with them when dealt with $\mathrm{3SAT}$).
So suppose that $\varphi_G$ is satisfiable. Then $s$ must be True in order to satisfy the clause $(s)$ and $t$ must be False to satisfy $(\overline t)$. However, if there is a path from $s$ to $t$, then every literal corresponding to a vertex on the path has to evaluate to True, which means that $t$ needs to be set to True, which is a contradiction.
Now suppose that there is no path from $s$ to $t$. Then we can set $s$ to True and $t$ to False. Since there is no path from $s$ to $t$, the implication chain from $s$ doesn't affect the assignment of $t$. With that taken care of, we can assign the rest of the variables, since by our construction there is no literal and its negation on the same path in $G$. Thus, we have a satisfying assignment. $$\tag*{$\Box$}$$