although the dfs complete function makes multiple calls to the original dfs functionthe total time spent by call to dfs complete is ( mfor an undirected graphrecall from our original analysis on page that single call to dfs starting at vertex runs in time (ns ms where ns is the number of vertices reachable from sand ms is the number of incident edges to those vertices because each call to dfs explores different componentthe sum of ns ms terms is the ( mtotal bound applies to the directed case as welleven though the sets of reachable vertices are not necessarily disjoint howeverbecause the same discovery dictionary is passed as parameter to all dfs callswe know that the dfs subroutine is called once on each vertexand then each outgoing edge is explored only once during the process the dfs complete function can be used to analyze the connected components of an undirected graph the discovery dictionary it returns represents dfs forest for the entire graph we say this is forest rather than treebecause the graph may not be connected the number of connected components can be determined by the number of vertices in the discovery dictionary that have none as their discovery edge (those are roots of dfs treesa minor modification to the core dfs method could be used to tag each vertex with component number when it is discovered (see exercise - the situation is more complex for finding strongly connected components of directed graph there exists an approach for computing those components in ( mtimemaking use of two separate depth-first search traversalsbut the details are beyond the scope of this book detecting cycles with dfs for both undirected and directed graphsa cycle exists if and only if back edge exists relative to the dfs traversal of that graph it is easy to see that if back edge existsa cycle exists by taking the back edge from the descendant to its ancestor and then following the tree edges back to the descendant converselyif cycle exists in the graphthere must be back edge relative to dfs (although we do not prove this fact herealgorithmicallydetecting back edge in the undirected case is easybecause all edges are either tree edges or back edges in the case of directed graphadditional modifications to the core dfs implementation are needed to properly categorize nontree edge as back edge when directed edge is explored leading to previously visited vertexwe must recognize whether that vertex is an ancestor of the current vertex this requires some additional bookkeepingfor exampleby tagging vertices upon which recursive call to dfs is still active we leave details as an exercise ( -