Topological Sort

3.5

11 votes
Graph Theory, Graph, Priority queue, Easy-Medium, Topological sorting
Problem

Given a Directed and Acyclic Graph having N vertices and M edges, print topological sorting of the vertices.

Input:
First line consists of two space separated integers denoting N and M.
Each of the following M lines consists of two space separated integers X and Y denoting there is an from X directed towards Y.

Output:
Print N space separated integers denoting the topological sort, if there are multiple ordering print the lexicographically smallest one.

Constraints:
1N10
1M20
1X,YN

Sample Input
5 6
1 2
1 3
2 3
2 4
3 4
3 5
Sample Output
1 2 3 4 5 
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?