Assume the input graph is directed but may or may not have cycle in it, that is, may or may not be a directed acyclic graph. Consider the recursive topological sorting algorithm shown below. TopologicalSort(G) { If G has only one node v then return v. Find a node v with no incoming edge and remove v from G. Return v followed by the order returned by TopologicalSort(G). }

(a) Extend the recursive algorithm shown below so it can detect and output a cycle if the input graph G is not a directed acyclic graph. Clearly mark the extended part of the algorithm and state your reasoning behind the extension made. Hint: Lemma 3.19 in the textbook.

(b) Additionally, explain how you can keep the running time O(m+n) with the extension.

please handle these two questions