Cod sursa(job #647107)

Utilizator tak3rStefan Mirea tak3r Data 11 decembrie 2011 12:37:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<list>

#define NMAX 50005

#define S_WHITE 0
#define S_GRAY  1
#define S_BLACK 2

using namespace std;

int N, *State, *Order, *InDegree, Pos = 0;
list<int> M[ NMAX ];

void read();
void topologic( int );
void write();
void clean();

int main(){
  read();
  for( int i=1; i<=N; ++i ){
    topologic( i );
  }
  write();
  clean();
  return 0;
}

void read(){
  freopen( "sortaret.in", "r", stdin );
  int m;
  scanf( "%d %d", &N, &m );
  
  State     = (int *) malloc( (N+1) * sizeof( int ) );
  Order     = (int *) malloc( (N+1) * sizeof( int ) );
  InDegree  = (int *) malloc( (N+1) * sizeof( int ) );
  
  memset( State, S_WHITE, (N+1) * sizeof( int ) );
  memset( InDegree, 0, (N+1) * sizeof( int ) );
  
  for( int i=0; i<m; ++i ){
    int a,b;
    scanf("%d %d", &a, &b );
    M[a].push_back( b );
    ++InDegree[ b ];
  }
  
}

void topologic( int p ){
  if( State[p] == S_WHITE ){
    //fprintf( stderr, " # topologic(%d): size:%d \n ", p+1, M[p].size() );
    list< int >::iterator it;
    State[ p ] = S_GRAY;
    for( it=M[p].begin(); it!=M[p].end(); ++it ){
      topologic( *it );
    }
    State[ p ]      = S_BLACK;
    Order[ N-Pos ]  = p;
    ++Pos;
  }
}

void write(){
  freopen( "sortaret.out", "w", stdout );
  for( int i=1; i<=N; ++i ){
    printf("%d ", Order[i]);
  }
}

void clean(){
  free( State );
  free( Order );
  free( InDegree );
}