TOPOSORT  Topological Sorting
Sandro is a well organised person. Every day he makes a list of things which need to be done and enumerates them from 1 to n. However, some things need to be done before others. In this task you have to find out whether Sandro can solve all his duties and if so, print the correct order.
Input
In the first line you are given an integer n and m (1<=n<=10000, 1<=m<=1000000). On the next m lines there are two distinct integers x and y, (1<=x,y<=10000) describing that job x needs to be done before job y.
Output
Print "Sandro fails." if Sandro cannot complete all his duties on the list. If there is a solution print the correct ordering, the jobs to be done separated by a whitespace. If there are multiple solutions print the one, whose first number is smallest, if there are still multiple solutions, print the one whose second number is smallest, and so on.
Example 1
Input: 8 9 1 4 1 2 4 2 4 3 3 2 5 2 3 5 8 2 8 6 Output: 1 4 3 5 7 8 2 6
Example 2
Input: 2 2 1 2 2 1 Output: Sandro fails.
hide comments
amantu_amir:
20200226 17:14:18
AC using Binary Search and Topological sort. 

md_meraj1319:
20200210 20:59:57
AC in 1 go. just use topological sort with Set in place of Queue. 

thakkar2804:
20200201 13:09:29
sort the adjacency list in descending order and then apply dfs for n to 1. 

nadstratosfer:
20200128 00:24:38
It's possible with Python:


luciusd:
20200127 21:56:49
Using Python 3.7.3, implement this problem with Kahn and Priorityqueue, but I got Time limit exceeded, any idea??? 

hetp111:
20191220 14:32:58
It should be mentioned if the graph is connected or not... Last edit: 20191220 14:33:27 

mt6170078:
20191017 21:42:03
java is giving TLE even after using priority queue... :'( Last edit: 20191017 21:42:25 

daasdaham80:
20190628 09:08:31
Cool problem, i learned kahns algo and priority queue in one go 

harshraj22aug:
20190625 21:25:04
Learnt Kahn's algorithm. Great question to try after learning it . 

akashbhalotia:
20190523 14:26:18
How to do this using DFS method?

Added by:  Josef Ziegler 
Date:  20111023 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 