Pagini recente » Cod sursa (job #989902) | Cod sursa (job #2039522) | Cod sursa (job #2511778) | Cod sursa (job #178373) | Cod sursa (job #647107)
Cod sursa(job #647107)
#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 );
}