Rezolvare PBinfo #2768

Cerința

Se consideră un graf orientat aciclic cu n noduri și m arce. Să se determine sortarea topologică a nodurilor grafului, minimă lexicografic.

Date de intrare

Programul citește de la tastatură numerele n și m, iar apoi m perechi de numere naturale, separate prin spații, x y cu semnificația: există în graful orientat arcul (x, y).

Date de ieșire

Programul va afișa pe ecran, separate prin câte un spațiu, nodurile grafului în ordinea lexicografică a acestora.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ m ≤ 500.000
• Este garantat că graful orientat este aciclic, deci va exista o soluție

Exemplu:

Intrare

6 7
3 6
3 1
6 1
5 1
2 5
4 1
4 2

Ieșire

3 4 2 5 6 1

Explicație

Digraful din exemplu este cel de mai jos.

Există mai multe soluții, precum 4,3,6,2,5,1, dar această soluție este mai mare din punct de vedere lexicografic.