# PBinfo #2768 – SortTopMinLex – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
vector<int> L[Nmax];
int n, m;
set<int> S;
/// in S se depun nodurile de grad interior 0
int d[Nmax]; /// d[i]=gradul interior al nodului i
void Citire()
{
    int i, x, y;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        cin >> x >> y;
        L[x].push_back(y);
        d[y]++;
    }
}
void SortTop()
{
    int i, nod;
    /// punem in S toate nodurile de grad 0
    for (i = 1; i <= n; i++)
        if (d[i] == 0)
            S.insert(i);
    while (S.size() > 0)
    {
        /// extrag din S nodul minim
        nod = *(S.begin());
        /// sterg nodul din stiva:
        S.erase(nod);
        cout << nod << " ";
        /// parcurgem lista de adiacenta a nodului nod
        /// si decrementam gradele tuturor nodurilor adiacente cu nod
        for (auto j : L[nod])
        {
            d[j]--;
            if (d[j] == 0)
                S.insert(j);
        }
    }
}
int main()
{
    Citire();
    SortTop();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2768)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2768/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2768/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)