A directed graph is strongly connected if there is a path from every vertex to every other vertex. Do the following.  a. Pick any vertex S. Show that, if the graph is strongly connected, a...

A directed graph is strongly connected if there is a path from every vertex to every other vertex. Do the following.

 a. Pick any vertex S. Show that, if the graph is strongly connected, a shortest-path algorithm will declare that all nodes are reachable from S.

b. Show that, if the graph is strongly connected and then the directions of all edges are reversed and a shortest-path algorithm is run from S, all nodes will be reachable from S.

 c. Show that the tests in parts (a) and (b) are sufficient to decide whether a graph is strongly connected (i.e., a graph that passes both tests must be strongly connected).

 d. Write a program that checks whether a graph is strongly connected. What is the running time of your algorithm?