Pagini recente » Cod sursa (job #3193997) | Cod sursa (job #3298184) | Cod sursa (job #180107) | Cod sursa (job #2718777) | Cod sursa (job #1117644)
#include <stdio.h>
#define N_MAX 50000
#define M_MAX 100000
int N, M, sp, anssp;
int list[ M_MAX + 1 ], next[ M_MAX + 1 ], beg[ N_MAX + 1 ], end[ N_MAX + 1 ];
int deg[ N_MAX + 1 ], ans[ N_MAX + 1 ];
void add( int s, int f ) {
list[ ++ sp ] = f;
if( beg[ s ] ) {
next[ end[ s ] ] = sp;
end[ s ] = sp;
} else {
beg[ s ] = end[ s ] = sp;
}
}
void tsort( ) {
int i, x;
for( i = 1; i <= N; i ++ ) {
if( deg[ i ] == 0 ) {
ans[ ++ anssp ] = i;
}
}
for( i = 1; i <= N; i ++ ) {
x = ans[ i ];
int curr = beg[ x ];
while( curr ) {
if( ( -- deg[ list[ curr ] ] ) == 0 ) {
ans[ ++ anssp ] = list[ curr ];
}
curr = next[ curr ];
}
}
}
int main( ) {
FILE * fin, * fout;
fin = fopen( "sortaret.in", "r" );
fout = fopen( "sortaret.out", "w" );
fscanf( fin, "%d%d", &N, &M );
int i;
for( i = 1; i <= M; i ++ ) {
int s, f;
fscanf( fin, "%d%d", &s, &f );
add( s, f );
}
tsort( );
for( i = 1; i <= N; i ++ ) {
fprintf( fout, "%d ", ans[ i ] );
}
fclose( fin );
fclose( fout );
}