Pagini recente » Cod sursa (job #2651072) | Cod sursa (job #1705875) | Cod sursa (job #25027) | Cod sursa (job #1651411) | Cod sursa (job #1494209)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
const int nmax = 100000;
int f[ nmax + 1 ];
vector< int > ord;
vector< int > gp[ nmax + 1 ], gm[ nmax + 1 ];
vector< int > c;
vector< vector< int > > C;
void dfs_plus( int nod ) {
f[ nod ] = 1;
for( vector< int >::iterator it = gp[ nod ].begin(); it != gp[ nod ].end(); ++ it ) {
if ( f[ *it ] == 0 ) {
dfs_plus( *it );
}
}
ord.push_back( nod );
}
void dfs_minus( int nod ) {
c.push_back( nod );
f[ nod ] = 2;
for( vector< int >::iterator it = gm[ nod ].begin(); it != gm[ nod ].end(); ++ it ) {
if ( f[ *it ] == 1 ) {
dfs_minus( *it );
}
}
}
int main() {
int n, m, x, y;
fin >> n >> m;
for( int i = 0; i < m; ++ i ) {
fin >> x >> y;
gp[ x ].push_back( y );
gm[ y ].push_back( x );
}
for( int i = 1; i <= n; ++ i ) {
if ( f[ i ] == 0 ) {
dfs_plus( i );
}
}
for( int i = ( int )ord.size() - 1; i >= 0; -- i ) {
if ( f[ ord[ i ] ] == 1 ) {
c.clear();
dfs_minus( ord[ i ] );
C.push_back( c );
}
}
fout << ( int )C.size() << "\n";
for( int i = 0; i < ( int )C.size(); ++ i ) {
for( vector< int >::iterator it = C[ i ].begin(); it != C[ i ].end(); ++ it ) {
fout << *it << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}