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.

#include <bits/stdc++.h>


using namespace std;

vector <int> G[100002];
set <int> Q;
int n , m , x , y , g[100002];

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        g[y]++;
    }

    for(int i = 1 ; i <= n ; i++)
        if(g[i] == 0)Q.insert(i);

    while(!Q.empty())
    {
        x = *(Q.begin());
        Q.erase(x);
        cout << x << " ";
        for(int i : G[x])
        {
            g[i]--;
            if(g[i] == 0) Q.insert(i);
        }

    }



}