Cod sursa(job #2487672)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 5 noiembrie 2019 17:29:52
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
#define NMAX 50005

using namespace std;

ifstream f ("sortaret.in");
ofstream g ("sortaret.out");

unsigned short n , x , y;
int m;
vector < vector < unsigned short > > a(NMAX);
queue < unsigned short > q;
int vec[50005];

int main()
{
    unsigned short i;

    f >> n >> m;

    for(i = 1 ; i <= m ; i++)
    {
        f >> x >> y;
        a[x].push_back(y);
        ++vec[y];
    }

    for(i = 1 ; i <= n ; i++)
        if(vec[i] == 0)
            q.push(i);

    unsigned nod = 0;

    while(!q.empty())
    {
        nod = q.front();
        q.pop();
        g << nod << ' ';

        for(i = 0 ; i < a[nod].size() ; i++)
        {
            if(--vec[a[nod][i]] == 0)
                q.push(a[nod][i]);
        }
    }

    return 0;
}