Pagini recente » Cod sursa (job #1944032) | Cod sursa (job #1656187) | Cod sursa (job #1498858) | Cod sursa (job #1217697) | Cod sursa (job #1382717)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
const int nmax = 100000;
int ii;
int index[ nmax + 1 ], lowlink[ nmax + 1 ];
bool in_stiva[ nmax + 1 ];
vector< int > g[ nmax + 1 ], c;
vector< vector< int > > C;
stack< int > st;
inline int min2( int a, int b ) {
if ( a < b ) {
return a;
}
return b;
}
void tarjan( int nod ) {
index[ nod ] = ii;
lowlink[ nod ] = ii;
++ ii;
st.push( nod );
in_stiva[ nod ] = 1;
for( vector< int >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
if ( index[ *it ] == -1 ) {
tarjan( *it );
lowlink[ nod ] = min2( lowlink[ *it ], lowlink[ nod ] );
} else if ( in_stiva[ *it ] == 1 ) {
lowlink[ nod ] = min2( lowlink[ *it ], lowlink[ nod ] );
}
}
if ( index[ nod ] == lowlink[ nod ] ) { /// este radacina
c.clear();
int k;
do {
k = st.top(); st.pop();
in_stiva[ k ] = 0;
c.push_back( k );
} while ( k != nod );
C.push_back( c );
}
}
int main() {
int n, m, x, y;
fin >> n >> m;
for( int i = 0; i < m; ++ i ) {
fin >> x >> y;
g[ x ].push_back( y );
}
for( int i = 1; i <= n; ++ i ) {
index[ i ] = -1;
}
ii = 1;
for( int i = 1; i <= n; ++ i ) {
if ( index[ i ] == -1 ) {
tarjan( i );
}
}
fout << C.size() << "\n";
for( int i = 0; i < ( int )C.size(); ++ i ) {
for( int j = 0; j < ( int )C[ i ].size(); ++ j ) {
fout << C[ i ][ j ] << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}