Topological sort P14952


Statement
 

pdf   zip

html

We must perform n tasks, one at a time. Furthermore, some tasks must be done before others: there are m precedence relations between tasks. Write a program to print a way to sort the n tasks satisfying the m given precedences.

Input

Input consists of several cases. Every case begins with n, followed by m, followed by m distinct pairs x y that indicate that task x must be done before task y. You can assume 1 ≤ n ≤ 104, 0 ≤ m ≤ 10n, and that the tasks are numbered from 0 to n − 1.

Output

For every case, print the lexicographically smallest order of the n tasks that fulfills the m given precedences. There will always be, at least, one solution.

Public test cases
  • Input

    3 1
    1 0
    
    1 0
    
    10 18
    0 3  4 8
    8 3  2 1
    5 7  5 6
    6 8  4 2
    4 0  8 1
    2 8  3 1
    6 2  7 3
    7 2  5 0
    0 6  9 5
    

    Output

    1 0 2
    0
    4 9 5 0 6 7 2 8 3 1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python