Pagini recente » Cod sursa (job #1004290) | Cod sursa (job #2576900) | Cod sursa (job #2926211) | Cod sursa (job #1595441) | Cod sursa (job #406777)
Cod sursa(job #406777)
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;
#define MAX_N 100005
#define MAX_S 10005
char s[ MAX_S ];
int xXx;
int N, M;
int cnt_s, ant[ MAX_N ];
bitset <MAX_N> f;
vector <int> sol[ MAX_N ], v_1[ MAX_N ], v_2[ MAX_N ];
inline void df_1( const int &nod ) {
vector <int> :: iterator it;
f[ nod ] = true;
for( it = v_1[ nod ].begin(); it != v_1[ nod ].end(); ++it )
if( f[ *it ] == false )
df_1( *it );
ant[ ++ant[ 0 ] ] = nod;
}
inline void df_2( const int &nod ) {
vector <int> :: iterator it;
f[ nod ] = false;
sol[ xXx ].push_back( nod );
for( it = v_2[ nod ].begin(); it != v_2[ nod ].end(); ++it )
if( f[ *it ] == true )
df_2( *it );
}
inline void read( int &val ) {
while( !isdigit( s[ cnt_s ] ) )
if( ++cnt_s == MAX_S ) {
fread( s, 1, MAX_S, stdin );
cnt_s = 0;
}
val = 0;
while( isdigit( s[ cnt_s ] ) ) {
val = val*10 + s[ cnt_s ] - '0';
if( ++cnt_s == MAX_S ) {
fread( s, 1, MAX_S, stdin );
cnt_s = 0;
}
}
}
int main() {
freopen( "ctc.in", "r", stdin );
freopen( "ctc.out", "w", stdout );
int i, x, y;
vector <int> :: iterator it;
cnt_s = MAX_S - 1;
read( N );
read( M );
while( M-- ) {
read( x );
read( y );
v_1[ x ].push_back( y );
v_2[ y ].push_back( x );
}
for( i = 1; i <= N; ++i )
if( f[ i ] == false )
df_1( i );
for( i = N; i > 0; --i )
if( f[ ant[ i ] ] == true ) {
++xXx;
df_2( ant[ i ] );
}
printf( "%d\n", xXx );
while( xXx ) {
for( it = sol[ xXx ].begin(); it != sol[ xXx ].end(); ++it )
printf( "%d ", *it );
printf( "\n" );
--xXx;
}
return 0;
}