Ordenació topològica P14952


Statement
 

pdf   zip

thehtml

Cal realitzar n tasques, d’una en una. A més, cal fer algunes tasques abans que altres: hi ha m relacions de precedència entre les tasques. Feu un programa que escrigui una manera d’ordenar les n tasques d’acord amb les m precedències donades.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, seguit de m, seguit de m parells diferents x y, que indiquen que cal realitzar la tasca x abans que la y. Suposeu 1 ≤ n ≤ 104, 0 ≤ m ≤ 10n, i que les tasques es numeren entre 0 i n − 1.

Sortida

Per a cada cas, escriviu la manera més petita lexicogràficament d’ordenar les n tasques d’acord amb les m precedències donades. Sempre hi haurà, com a mínim, una solució.

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
    Catalan
    Other languages
    English
    Official solutions
    C++ Python Python
    User solutions
    C++ Python