Cod sursa(job #149677)

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

struct point { int v; point *l; } *G[MAXN];
int S[MAXN], U[MAXN], n, m, s;
void Df ( int x )
{
    point *p;
    U[x]=1;
    for ( p=G[x] ; p ; p=p->l )
        if (!U[p->v]) Df(p->v);
    S[s--]=x;
}

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 = y;
        p->l = G[x];
        G[x] = p;
    }
    fclose ( stdin );
}

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

int main ()
{
    read_data ();
    s=n;
    int i;
    for ( i=1 ; i<=n ; i++ ) if (!U[i] ) Df(i);
    write_data ();
    return 0;
}