Ordenacions topològiques P62138


Statement
 

pdf   zip

html

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 totes les maneres possibles d’ordenar les n tasques d’acord amb les m precedències donades.

Entrada

L’entrada consisteix en un natural n ≥ 1, seguit d’un natural m, seguit de m parells diferents x, y, que indiquen que cal realitzar la tasca x abans que la y. Suposeu que les tasques es numeren entre 0 i n − 1.

Sortida

Escriviu, una per línia i en ordre lexicogràfic, totes les maneres 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

    Output

    1 0 2
1 2 0
2 1 0

  • Input

    1 0

    Output

    0

  • Input

    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

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