Tasks depend on each other: an edge u v means "u must be done before v". Write CycleFinder. Read n m and m directed edges. Run DFS from vertices 0, 1, 2, … visiting neighbours in increasing order, with three colours: white (unvisited), gray (on the current path), black (finished).
- An edge to a gray vertex closes a cycle: print it (from that vertex back to itself, following the DFS path) and
No valid order exists. - If there is no cycle, print
No cycle (the graph is a DAG)and a topological order (reverse order of finishing).
For the input
5 5
0 1
1 2
2 3
3 1
0 4
the program prints
Cycle found: 1 -> 2 -> 3 -> 1
No valid order exists
A DAG usually has several valid orders, so for acyclic graphs the tests check only the first line.