Cod sursa(job #1612421)

Utilizator coolyonutzepure ionut coolyonutz Data 24 februarie 2016 20:46:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#include <vector>

#define NMAX 50001

using namespace std;

int grad[NMAX], q[NMAX], i, j, n, m;
vector <int> G[NMAX];





int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d %d",&n, &m);
    for(i=1; i<=m; i++)
    {
        int nod1,nod2;

        scanf("%d %d",&nod1, &nod2);
        G[nod1].push_back(nod2);
        grad[nod2]++;
    }

    for(i=1; i<=n; i++) if(grad[i]==0) q[++q[0]]=i;

    for(i=1; i<=n; i++)
    {
        int vf=q[i];
        int k=G[vf].size();

        for(j=0; j<k; j++)
        {
            grad[G[vf][j]]--;
            if(!grad[G[vf][j]]) q[++q[0]]=G[vf][j];
        }
    }

    for(i=1; i<=n; i++) printf("%d ",q[i]);

}