Cod sursa(job #149676)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 5 martie 2008 23:21:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#define MAXN 50001

struct point { int v; point *l; } *G[MAXN];
int S[MAXN], Deg[MAXN], n, m, s;

void read_data ()
{
    point *p;
    int x,y,i;
    freopen ( "sortaret.in" , "r" , stdin );
    scanf ( "%d %d" , &n , &m );
    for ( i=0 ; i<m ; i++ )
    {
        scanf ( "%d %d" , &x , &y );
        p = new point;
        p->v = x;
        p->l = G[y];
        G[y] = p;
        Deg [x]++;
    }
    fclose ( stdin );
}

void write_data ()
{
    int i;
    freopen ( "sortaret.out" , "w" , stdout );
    for ( i=n ; i-1 ; i-- ) printf ( "%d " , S[i] );
    printf ( "%d\n" , S[1] );
    fclose ( stdout );
}

void sortare ()
{
    int i;
    point *p;
    for ( s=i=1 ; i<=n ; i++ )
        if (Deg[i]==0) S[s++]=i;
    for ( i=1 ; i<s ; i++ )
        for ( p=G[S[i]] ; p ; p=p->l )
        {
            Deg[p->v]--;
            if (Deg[p->v] ==0) S[s++]=p->v;
        }
}

int main ()
{
    read_data ();
    sortare();
    write_data ();
    return 0;
}