Description
Problem 1[100 pts] Write a program that takes as input a directed graph (in the format described below) and outputs
(I) ‘YES’ or ‘NO’ depending on whether the graph is a DAG, and, (II) in case it is a DAG, it outputs a linear ordering
of the DAG, and, (III) in case it is a DAG, outputs the length of the longest path in the DAG starting from vertex 1.
The input will consist of several lines and will be given either as a text file or on the command prompt. The first line will
be a positive integer n. This is the number of vertices of the graph – the names of the vertices will be 1, 2, 3, . . . , n. The
next few lines will contain the edges of the graph as i, j where 1 ≤ i ≤ n and 1 ≤ j ≤ n and i 6= j. You can rest assured
that the input will be in the correct format and as expected. A valid input could be for example:
5
1,2
3,4
3,1
For the input above, one possible correct output is:
YES
3, 1, 4, 2, 5
1
An example of an incorrect input that you will never see is:
5
0, 1
a, 1
1