Pagini recente » Cod sursa (job #1316090) | Cod sursa (job #3123439) | Cod sursa (job #2612736) | Cod sursa (job #1847480) | Cod sursa (job #2660336)
#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
const int nMax = 50001;
vector< int > v[nMax];
vector< pair< int, int>> grad;
class inputParser {
static const unsigned int buffSize = 1 << 17;
unsigned int pozBuff;
FILE *fin;
unsigned char *buffer;
void getChar( unsigned char &ch ) {
if ( pozBuff == buffSize ) {
pozBuff = 0;
assert( fread( buffer, sizeof( char ), buffSize, fin ) );
}
ch = buffer[ pozBuff++ ];
}
public:
explicit inputParser( const char *fileName ) {
fin = fopen( fileName, "r" );
assert( fin != nullptr );
buffer = new unsigned char[buffSize];
pozBuff = buffSize;
}
inputParser( const inputParser &dummy ) = delete;
inputParser &operator=( const inputParser &dummy ) = delete;
template < class intType >
inputParser &operator>>( intType &nr ) {
int sgn( 1 );
unsigned char ch;
nr = 0;
getChar( ch );
while ( isdigit( ch ) == 0 && ch != '-' )
getChar( ch );
if ( ch == '-' ) {
sgn = -1;
getChar( ch );
}
while ( isdigit( ch ) != 0 ) {
nr = nr * 10 + ch - '0';
getChar( ch );
}
nr *= sgn;
return *this;
}
inputParser &operator>>( char &ch ) {
unsigned char ch2;
do {
getChar( ch2 );
} while ( isgraph( ch2 ) == 0 );
ch = static_cast<char>(ch2);
return *this;
}
inputParser &operator>>( unsigned char &ch ) {
getChar( ch );
do {
getChar( ch );
} while ( isgraph( ch ) == 0 );
return *this;
}
~inputParser() {
fclose( fin );
delete[] buffer;
}
};
int dfs( int nod ) {
if ( v[ nod ].size() == 0 ) {
grad[ nod ].first = -1;
return -1;
}
else {
for ( unsigned i = 0; i < v[ nod ].size(); i++ ) {
grad[ nod ].first = min( grad[ nod ].first, dfs( v[ nod ][ i ] ) - 1 );
}
return grad[ nod ].first;
}
}
int main() {
int n, m;
inputParser fin( "sortaret.in" );
FILE *fout;
fin >> n >> m;
for ( int i = 0; i < m; i++ ) {
int a, b;
fin >> a >> b;
v[ a ].push_back( b );
}
for ( int i = 0; i <= n; i++ )
grad.push_back( { 0, i } );
for ( int i = 1; i <= n; i++ )
if ( grad[ i ].first == 0 )
dfs( grad[ i ].second );
sort( grad.begin(), grad.end() );
fout = fopen( "sortaret.out", "w" );
for ( unsigned i = 0; i < grad.size(); i++ )
if ( grad[ i ].second > 0 )
fprintf( fout, "%d ", grad[ i ].second );
fclose( fout );
return 0;
}