Cod sursa(job #2884572)

Utilizator TanasaStefanTanasa Stefan TanasaStefan Data 4 aprilie 2022 09:28:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector < int > v[100005];
int n , m , q[100005] , ext[100005] , nr;
int main()
{
    f >> n >> m;
    for (int i = 1 ; i <= m ; i++)
    {
        int x , y;
        f >> x >> y;
        v[x].push_back(y);
        ext[y]++;
    }
    nr = 0;
    for ( int i = 1 ; i <= n ; i++)
        if(ext[i] == 0)
            q[++nr] = i;
    for ( int i = 1 ; i <= n ; i++)
    {
        int k = q[i];
        for ( vector < int > :: iterator i = v[k].begin() ; i != v[k].end() ; i++)
        {
            ext[*i]--;
            if(ext[*i] == 0)
                q[++nr] = *i;
        }
    }
    for (int i = 1 ; i <= n ; i++)
        g << q[i] << " ";
}