and ms edges are reachable from vertex sa directed dfs starting at runs in ( timeprovided the digraph is represented with data structure that supports constant-time vertex and edge methods the adjacency list structure satisfies this requirementfor example by proposition we can use dfs to find all the vertices reachable from given vertexand hence to find the transitive closure of that iswe can perform dfsstarting from each vertex of to see which vertices are reachable from vadding an edge (vwto the transitive closure for each such likewiseby repeatedly traversing digraph easily test whether with dfsstarting in turn at each vertexwe can is strongly connected namelyis strongly connected if each dfs visits all the vertices of thuswe may immediately derive the proposition that follows proposition let be digraph with vertices and edges the following problems can be solved by an algorithm that traverses dfsruns in ( ( + )timeand uses (nauxiliary spacecomputingfor each vertex of testing whether computing the transitive closure times using the subgraph reachable from is strongly connected of testing for strong connectivity actuallywe can determine if directed graph is strongly connected much faster than thisjust using two depth-first searches we begin by performing dfs of our directed graph vertex of starting at an arbitrary vertex if there is any that is not visited by this dfsand is not reachable from sthen the graph is not strongly connected soif this first dfs visits each vertex of we reverse all the edges of then (using the reverse direction methodand perform another dfs starting at in this "reversegraph if every vertex of is visited by this second dfsthen the graph is strongly connectedfor each of the vertices visited in this dfs can reach since this algorithm makes just two dfs traversals of it runs in ( mtime