we may wish to test whether it is strongly connectedthat for directed graphgiswhether for every pair of vertices and vboth reaches and reaches if we start an independent call to dfs from each vertexwe could determine whether this was the casebut those calls when combined would run in ( (nm)howeveris strongly connected much faster than thisrequiring only we can determine if two depth-first searches starting at we begin by performing depth-first search of our directed graph an arbitrary vertex if there is any vertex of that is not visited by this traversaland is not reachable from sthen the graph is not strongly connected if this first we need to then check whether is reachdepth-first search visits each vertex of gable from all other vertices conceptuallywe can accomplish this by making but with the orientation of all edges reversed depth-first search copy of graph gstarting at in the reversed graph will reach every vertex that could reach in the original in practicea better approach than making new graph is to reimplement version of the dfs method that loops through all incoming edges to the current vertexrather than all outgoing edges since this algorithm makes just two dfs it runs in ( mtime traversals of gcomputing all connected components when graph is not connectedthe next goal we may have is to identify all of the connected components of an undirected graphor the strongly connected components of directed graph we begin by discussing the undirected case if an initial call to dfs fails to reach all vertices of graphwe can restart new call to dfs at one of those unvisited vertices an implementation of such comprehensive dfs all method is given in code fragment def dfs complete( ) """perform dfs for entire graph and return forest as dictionary result maps each vertex to the edge that was used to discover it (vertices that are roots of dfs tree are mapped to none "" forest for in vertices) if not in forest forest[unone will be the root of tree dfs(guforest return forest code fragment top-level function that returns dfs forest for an entire graph