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.

3. The algorithm described in Section 3.6 for computing a topological order- ing of a DAG repeatedly finds a node with no incoming edges and deletes it. This will eventually produce a topological ordering, provided that the input graph really is a DAG. But suppose that we're given an arbitrary graph that may or may not be a DAG. Extend the topological ordering algorithm so that, given an input directed graph G, it outputs one of two things: (a) a topological ordering, thus establishing that G is a DAG; or (b) a cycle in G, thus establishing that G is not a DAG. The running time of your algorithm should be O(m + n) for a directed graph with n nodes and m edges