Cod sursa(job #1196689)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 8 iunie 2014 19:38:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
using namespace std;
#include <fstream>
#include <vector>
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int Nmax = 50000;
vector<int> v[Nmax+1];
int g[Nmax+1], uz[Nmax+1], q[Nmax];


int main()
{
    int i, m, n, a, b, p=0, u=-1;
    vector<int>::iterator it;
    fin>>n>>m;
    for(; m; --m)
    {
        fin>>a>>b;
        v[b].push_back(a);
        g[a]++;
    }
    for(i=1; i<=n; ++i)
        if(!g[i]) q[++u] = i, uz[i] = 1;
    while(p<=u)
    {
        a = q[p]; ++p;

        for(it = v[a].begin(); it!=v[a].end(); ++it)
            if(!uz[*it])
            {
                --g[*it];
                if(g[*it]==0)
                    q[++u] = *it, uz[*it] = 1;
            }
    }
    for(i=u; i>=0; --i)
        fout<<q[i]<<' ';
    fout<<'\n';
    return 0;
}