Cod sursa(job #143995)

Utilizator TabaraTabara Mihai Tabara Data 27 februarie 2008 00:44:57
Problema Sortare topologica Scor Ascuns
Compilator cpp Status done
Runda Marime 1.53 kb
#include <fstream>
using namespace std;

#define in "sortaret.in"
#define out "sortaret.out"
#define NMAX 5005

#define ALB 0
#define GRI 1
#define NEGRU 2
#define INF 30000

typedef struct nod {
        int vf;
        nod* next;
} *PNOD, NOD;

PNOD L[NMAX];

typedef struct list {
        int vf;
        list* next;
} LIST, *PLIST;

PLIST adresa;

int color[NMAX], n, m;
int timp, td[NMAX], tf[NMAX];
int nod_p, nod_s;

void Read();
void DF(int);
void Add(int i, int j);
void Insert( int );

FILE *fout = fopen( out, "w" );

int main()
{
    Read();
    int i;
    for ( i = 1; i <= n; ++i )
        if ( color[i] == ALB ) DF(i);
                
    for ( PLIST i = adresa; i; i = i->next )
        fprintf( fout, "%d ", i->vf );
    fclose( fout );
    return 0;
}

void Read()
{
     FILE *fin = fopen( in, "r" );
     fscanf( fin, "%d%d", &n, &m );
     int i, x, y;
     for ( i = 1; i <= m; i++ )
     {
         fscanf( fin, "%d%d", &x, &y );
         Add(x,y);
     }
     fclose( fin );
}

void DF( int nod )
{
     color[nod] = GRI;
     td[nod] = ++timp;
     for ( PNOD j = L[nod]; j; j = j->next )
         if ( color[j->vf] == ALB )
         {
              DF( j->vf );
         }
     tf[nod] = ++timp;
     Insert( nod ); 
}
              
void Add( int i, int j)
{
     PNOD p = new NOD;
     p->vf = j;
     p->next = L[i];
     L[i] = p;
}

void Insert( int nod )
{
     PLIST p = new LIST;
     p->vf = nod;
     p->next = adresa;
     adresa = p;
}