Each vertex keeps track of three states: visited, in progress, done. We also keep track of when we going to enter it and when we are also be done

initialize vertex.state = UNVISITED across graph def dfs(vertex, currentTime): vertex.startTime = currentTime currentTime++ vertex.state = IN_PROGRESS for v in vertex.neightbors: if v.state == UNVISITED: # to prevent loops currentTime = dfs(v, currentTime) currentTime += 1 w.finishTime = currentTime w.state == DONE return currentTime This explores all connected component starting from each vertex, so presumably you have to repeatedly by iterating through all verticies.

runtime visit vertex in G exactly once at each vertex w, we do O\left(1\right) bookkeeping loop over w neighbors (one per neighbor) and recurse O\left(\text{deg}\left(w\right)\right) This gives \sum_{w \in V’}^{} O\left(\text{deg}\left(w\right)\right) + O\left(1\right) = O\left(|E|+|V|\right) = O\left(n+m\right) use cases topological sort see topological sort