Cod sursa(job #1121789)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 25 februarie 2014 14:04:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
#include <queue>

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,x1,y,x[nmax],nr,nrint[nmax],nc;

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

void sortare()
{
    queue <int> q;
    for (i=1;i<=n;i++) if (!nrint[i]) q.push(i);
    nr=0;
    while (!q.empty())
    {
        nc=q.front();
        nr++;
        x[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<<x[i]<<" ";
}

int main()
{
    citire();
    sortare();
    f.close();g.close();
    return 0;
}