TOPOSORT - Topological Sorting

no tags 

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.


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.


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

8 9
1 4
1 2
4 2
4 3
3 2
5 2
3 5
8 2
8 6
1 4 3 5 7 8 2 6 

Example 2

2 2
1 2
2 1
Sandro fails.

hide comments
deepak_bulani1: 2017-02-01 21:09:59

take care of the "." at the end of Sandro fails

abhishek: 2017-02-01 19:34:15

people getting WA for test 12 .. i think they need to change condition for "Sandro fails." i.e for cyclic check . Check wether your output consists of n nodes or not ...rather than checking for an empty queue ! :)

Last edit: 2017-02-01 19:36:33
rajeev_mnnit: 2017-02-01 19:07:04

set & scanf/printf in c++

Hacking to the Gate: 2017-01-31 05:27:18

AC with unordered_map & priority_queue O(|V|log|V| + |E|). <3 STL.

kmalhotra30: 2017-01-27 12:48:44

don't use cin/cout

da_201501181: 2017-01-13 22:33:45

Wrong answer on test case 12 for java Anyone Please Help..where i am missing..??

sina_ss: 2017-01-11 09:12:31

Nice dfs.
but the greedy algorithm :|

Last edit: 2017-01-11 09:30:17
Roger: 2017-01-11 03:36:56

Looks like to be too strict for JAVA.

jason721b: 2016-12-05 02:34:25

I am wondering whether it is possible to use Ruby to solve this. I kept getting TLE

vengatesh15: 2016-12-01 07:37:42

nice one :-)
if u r getting tle use list stl instead of set

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