# PBinfo #1861 – TopSort – Rezolvare C++

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

## Enunț

Cerința
Se dă un graf orientat aciclic cu N noduri numerotate de la 1 la N. Să se realizeze o sortare topologică a nodurilor.

Date de intrare
Fișierul de intrare topsort.in conține pe prima linie numerele N M, reprezentând numărul de noduri și numărul de arce din graf, iar pe următoarele M linii câte o pereche de noduri i j, cu semnificația că în graf există arcul (i j).

Date de ieșire
Fișierul de ieșire topsort.out va conține pe prima linie cele N noduri ale grafului, separate prin exact un spațiu, în ordinea dată de sortarea topologică.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ M ≤ 400.000

Exemplu:
topsort.in

7 10
1 2
2 5
3 4
3 5
4 5
7 1
7 2
7 4
7 5
7 6
topsort.out

7 6 3 4 1 2 5 
Explicație

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <cstring>
#define NN 100001
using namespace std;
fstream fin("topsort.in", ios::in), fout("topsort.out", ios::out);
int n, v[NN];
list<int> F;
vector<int> G[NN];
void dfs(int x){
    v[x] = 1;
    for(vector<int>::iterator I = G[x].begin(); I < G[x].end() ; I++)
        if(v[*I] == 0)
            dfs(*I);
    F.push_front(x);
}
int main(){
    fin >> n;
    int m;
    for(fin >> m ; m ; m --)
    {
        int x , y;
        fin >>x >> y;
        G[x].push_back(y);
    }
    for(int i = 1 ; i <= n ; i++)
        if(v[i] == 0)
            dfs(i);
    for(list<int>::iterator x = F.begin() ; x != F.end() ; x ++)
        fout << *x << " ";
    return 0;
}
```

## Resurse

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