DAGy is made up of a directed acyclic graph plus one additional directed edge. With this additional edge a cycle forms that goes through every vertex in the graph.
The first quote claims that there is "one additional edge" that forms a cycle and if that edge didn't exist there wouldn't be a cycle. The second quote doesn't exactly say anything about additional edge resulting in a cycle, however does it mean so?It is guaranteed that each input graph is a directed acyclic graph with one additional edge between two distinct vertices of graph.
DAGy can be put back in order if you find the maximal cycle that goes through every vertex.
This is the most confusing part to me, as it seems to me that in the second input there should be solution. Obviously the maximal cycle in the graph will have infinite number of edges. Consider a cycle that goes 0 - 1 - 2 - 0 - 3 - 2 - 0. Is it the maximal? No. So it makes me think by the maximal cycle problem setter means the cycle that goes through each edge only once, and "the" must be indicating that there must be only 1 such cycle. Hence, the solution to this problem is very simple - just check that all in-degrees and out-degrees are equal to one. Problem with that is that it seems too easy, and my solution gives WA. Note that there shouldn't not be more than one connected component in the graph, as it would result in non DAG and would contradict to the second quote.4 5
I'm clearly not understanding what the problem setter wanted us to find here. What do you guys think we have to find in this problem?