Given a directed acyclic graph(DAG) G = (V, E) which is just a directed simple path and jVj = n.

The topological sorting can be solved on G by doing DFS from the source node and numbering

nodes from n down to 1 when the DFS colors a node black, i.e., reverse post-ordering on the DFS

tree. If we are given another DAG G0 which are two node-disjoint simple paths, we can extend

G0 by creating a super source node and two edges from the super source to the two sources of

the paths. The topological sorting on extended G0 can be solved if we start a DFS from the super

source node and allocate numbers from n down to 0 in the manner described above. The super

source node will get the number 0, and all the other nodes will be topologically sorted from 1

to n. Given an arbitrary DAG G = (V, E), extend this idea to give an O(jEj) algorithm to solve

topological sorting on G by using DFS. Argue the correctness of your algorithm and its O(jEj) time

complexity.

4. Given a directed acyclic graph(DAG) G = (V,E) which is just a directed simple path and IV-n. The topological sorting can be solved on G by doing DFS from the source node and numbering nodes from n down to 1 when the DFS colors a node black, i.e., reverse post-ordering on the DFS tree. If we are given another DAG G which are two node-disjoint simple paths, we can extend G' by creating a super source node and two edges from the super source to the two sources of the paths. The topological sorting on extended G' can be solved if we start a DFS from the super source node and allocate numbers from n down to 0 in the manner described above. The super source node will get the number 0, and all the other nodes will be topologically sorted from 1 to n. Given an arbitrary DAG G-(V,E), extend this idea to give an O(IEl) algorithm to solve topological sorting on G by using DFS. Argue the correctness of your algorithm and its O(El) time complexity. 4. Given a directed acyclic graph(DAG) G = (V,E) which is just a directed simple path and IV-n. The topological sorting can be solved on G by doing DFS from the source node and numbering nodes from n down to 1 when the DFS colors a node black, i.e., reverse post-ordering on the DFS tree. If we are given another DAG G which are two node-disjoint simple paths, we can extend G' by creating a super source node and two edges from the super source to the two sources of the paths. The topological sorting on extended G' can be solved if we start a DFS from the super source node and allocate numbers from n down to 0 in the manner described above. The super source node will get the number 0, and all the other nodes will be topologically sorted from 1 to n. Given an arbitrary DAG G-(V,E), extend this idea to give an O(IEl) algorithm to solve topological sorting on G by using DFS. Argue the correctness of your algorithm and its O(El) time complexity