Exercise 2: Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. (It should not output all cycles in the graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges.

Do the Textbook Exercise 2 of Chapter 3. Note that the algorithm should find and output a cycle if there is one in the graph. Assume a connected graph. Use breadth-first search as the base of the algorithm. Assume the adjacency list representation of a graph. Consider the following points as given: Any edge of the graph G that is not included in the BFS tree T causes a cycle if added to T (see Figure 3.3(c) in the textbook for an illustration) BFS on a graph represented using an adjacency list takes O(m + n) (see Property 3.11 in the textbook). There is a linear-time algorithm for finding a lowest common ancestor (LCA) in a tree assume one is given. Give your answers according to the following specification: a) Outline the key idea of your algorithm design. b) Write your algorithm in pseudocode that is precise enough to be executable. c) Explain how you can implement the algorithm to run in time O(m + n). You should justify the running time complexity of each step in your algorithm.