A digraph is called "strongly connected", if between any two vertices there is a $($directed$)$ path. The simplest example for strongly connected digraphs is the $($directed$)$ cycle graph, that is$,$ for n $>=1$ we have the vertices $1,...,$n$,$ and the arcs $(1,2),(2,3),...,($n$-1,$n$),($n$,1).$

Now the task is to decide whether an input digraph G is strongly connected. Which of the following algorithms does the job $($using n $>=1$ for the number of vertices of G$)?$

For wrong ticks negative marks are given.

A digraph is called "strongly connected", if between any two vertices there is a $($directed$)$ path. The simplest example for strongly connected digraphs is the $($directed$)$ cycle graph, that is$,$ for n $>=1$ we have the vertices $1,...,$n$,$ and the arcs $(1,2),(2,3),...,($n$-1,$n$),($n$,1).$

Now the task is to decide whether an input digraph G is strongly connected. Which of the following algorithms does the job $($using n $>=1$ for the number of vertices of G$)?$

For wrong ticks negative marks are given.

Choose a start vertex s$.$

Run BFS with start vertex s$.$ If one of the distances is infinity, then G is not strongly connected, and the algorithm terminates.

Now obtain the new digraph G$\text{'}$ by keeping the vertices, while reversing the direction of the arcs.

Run BFS with start vertex s on G$\text{'}.$ The original G now is strongly connected iff in G$\text{'}$ none of the distances is infinity.

Run DFS$,$ without controlling the vertex order. If a restart was needed, then G is not strongly connected, and the algorithm terminates.

Obtain the new digraph G$\text{'}$ from G by keeping the vertices, while reversing the direction of the arcs. Run DFS on G$\text{'},$ again without controlling the vertex order. Now G is strongly connected, iff this run of DFS didn't need a restart.

Run BFS$,$ without controlling the vertex order. If from the start vertex $($which depends on the vertex order$)$ we can not reach every other vertex, then G is not strongly connected.

Otherwise obtain the new digraph G$\text{'}$ from G by keeping the vertices, while reversing the direction of the arcs. Run BFS on G$\text{'},$ again without controlling the vertex order. If from the start vertex $($which depends on the vertex order$)$ we can not reach every other vertex, then G is not strongly connected, while otherwise G is strongly connected.

Pick any vertex s$.$

Run DFS with start vertex s$.$ If finishing time of s is not $2$n$,$ then G is not strongly connected, and the algorithm terminates.

Now obtain the new digraph G$\text{'}$ by keeping the vertices, while reversing the direction of the arcs.

Run DFS with start vertex s on G$\text{'}.$ The original G now is strongly connected iff the finishing time of s is $($again$)2$n$.$