Lab 3.3: topological sort
You cannot submit for this problem because the homework's deadline is due.
Description
Use OCmal to implement topological sort. The given input refers to a Directed Acyclic Graph (DAG).
Submission Format
Submit a tar or zip file including a script named toposort.ml
.
IO Format
Input
The first line contains the number of vertices.
The second line contains the number of edges.
The following lines are all the edges in the DAG. Each line contains one edge (u,v)
, with direction from vertex u
to v
.
Output
Output the result of topological sort in one line. There might be many possible solutions for the DAG, only output one possible answer.
Please note that because of the special judge used in this problem, the case detail could not be shown. So you can not see the correct answer for each case.
Sample IO
For a DAG shown in the figure:
Input
6
7
0 2
1 5
5 4
5 2
3 2
0 5
1 3
Output
This is one possible output.
0 1 5 4 3 2
Output on of the following answers would be accepted
['0 1 3 5 2 4', '0 1 3 5 4 2', '0 1 5 3 2 4', '0 1 5 3 4 2', '0 1 5 4 3 2', '1 0 3 5 2 4', '1 0 3 5 4 2', '1 0 5 3 2 4', '1 0 5 3 4 2', '1 0 5 4 3 2', '1 3 0 5 2 4', '1 3 0 5 4 2']