1. Traversal Applications. a.) (10 points) Modify the Depth-first Search (DFS) algorithm so that it can detect whether a cycle in any given directed unweighted graph G = (V, E). You can start with the DFS pseudocode in the slides and create a new modified version DFS CYC(V,E) that takes as input the graph and returns TRUE if there is a cycle or FALSE otherwise. What is the running time of your algorithm?

n BES(V, E,s): for each vertex v E V {S} V.state = unvisited, v. dist = co, v.pred = null s.state = visited, s. dist = 0, s. pred = null Set queue Q = null ENQUEUE(Q,s) while Q # null v = DEQUEUE(Q) for each u Adj[v] if u. state == unvisited u.state = visited u.dist = v.dist + 1 u.pred = V ENQUEUE(Q, U) v.state = complete