Please note!! This is only one question, I explained the question in the detailed formated with instructions and example, you only have to edit the given code to get the similar output in the example. Please answer it in step by step format. Thank you!!

Finding a cycle in a directed graph using depth-first search. A directed graph is a graph where edges are directional; that is, edges (p,q) and (q,p) are distinct. An important class of directed graphs are directed acyclic graphs (DAGs), which have broad applications in programming languages and compilers. A DAG is any directed graph with no cycles. For example, this is a directed graph:

The above graph is not a DAG because it contains cycles. The cycles are:

1 2 4 7 4 5 7 

By extension, these rotated versions are also valid cycles of the above graph (and they are all such possible rotations):

2 1 7 4 5 7 4 7 4 5 

In this final part of the assignment, you will bring together ideas you have used throughout this assignment to find and print a cycle in a directed graph. If no cycles are found, your program will report that the graph is a DAG. You can use any algorithm for this task; either the DFS or the BFS approaches you have used in this assignment so far can be useful.

Input

Your program should take a single command line argument specifying the path to an input file. Test cases for your program are in the tests/ directory. In each test case, the first line records the number of nodes N in the graph. Then, the adjacency matrix is recorded in the subsequent N rows of the file. This time, the adjacency matrix represents a directed graph.

Output

You should print a single line of nodes (separated by spaces) that forms a cycle in the input directed graph. For example, for the example directed graph above you can print any one of the seven cycles listed above. This time, the ordering of the nodes does matter as this is a directed graph. If no cycles were found, your program should print "DAG", meaning the graph is acyclic. The known cycles for each test case are in the answers/ directory. You can print out rotated versions of the known cycles; the autograder will see that rotated cycles are equivalent.

Edit the given code below:

#include "../graphutils.h"

// A program to find a cycle in a directed graph

// You may use DFS or BFS as needed

/* ... */

int main ( int argc, char* argv[] ) {

// READ INPUT FILE TO CREATE GRAPH ADJACENCY LIST

AdjacencyListNode* adjacencyList;

/* ... */

bool isCyclic = false;

for (unsigned source=0; source

/* ... */

}

if (!isCyclic) { printf("DAG "); }

freeAdjList ( graphNodeCount, adjacencyList );

return EXIT_SUCCESS;

}