Cod sursa(job #1343719)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 15 februarie 2015 20:34:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

fstream f("sortaret.in",ios::in);
fstream g("sortaret.out",ios::out);

const int nmax = 50005;

vector <int> a[nmax];

int n, m, i, x, y, nrint[nmax], a1[nmax], nr, nc;

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

void rezolvare()
{
    queue <int> q;
    for (i = 1; i <= n; i++) if (!nrint[i]) q.push(i);
    while (!q.empty())
    {
        nc = q.front();
        nr++;
        a1[nr] = nc;
        q.pop();
        for (vector <int>::iterator it = a[nc].begin();it != a[nc].end(); ++it)
        {
            nrint[*it]--;
            if (!nrint[*it]) q.push(*it);
        }
    }
    for (i = 1; i <= n; i++) g<<a1[i]<<" ";
}


int main()
{
    citire();
    rezolvare();
    return 0;
}