Cod sursa(job #164443)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 24 martie 2008 11:09:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <queue>

using namespace std;

#define FIN "sortaret.in"
#define FOUT "sortaret.out" 
#define MAXN 50001

int N[MAXN];
queue <int> Q;
struct point {int v; point *l;} *G[MAXN];

int main()
{
    int n,m,i,x,y;
    point *p;
    freopen(FIN , "r" , stdin);
    scanf("%d %d" , &n , &m);
    while (m--)
    {
        scanf ("%d %d" , &x , &y );
        N[y]++; p = new point; p->v=y;
        p->l=G[x]; G[x]=p; 
    }
    fclose(stdin);

    freopen (FOUT , "w" , stdout);
    for ( i=0 ; i<n ; )
        if (!N[++i]) Q.push(i);
    while (!Q.empty())
    {
        printf ( "%d " , Q.front() );
        for ( p=G[Q.front()] ; p ; p=p->l )
            if (!--N[p->v]) Q.push(p->v);
        Q.pop();
    }
    fclose(stdout);

    return 0;
}