Pagini recente » Cod sursa (job #959627) | Cod sursa (job #836383) | Cod sursa (job #827715) | Cod sursa (job #2513632) | Cod sursa (job #1890482)
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100005
stack < int > Q;
vector < int > v[ NMAX ];
vector < vector < int > > sol;
int lowBound[ NMAX ];
int upBound[ NMAX ];
int inStack[ NMAX ];
int pas;
void CTC ( int nod ) {
int i, j, k;
vector < int > aux;
vector < int > :: iterator it;
lowBound[ nod ] = upBound[ nod ] = ++pas;
inStack[ nod ] = 1;
Q.push( nod );
for ( it = v[ nod ].begin(); it != v[ nod ].end(); ++it ) {
if ( !lowBound[ *it ] ) {
CTC( *it );
lowBound[ nod ] = min ( lowBound[ nod ], lowBound[ *it ] );
} else if ( inStack[ *it ] ){
lowBound[ nod ] = min ( lowBound[ nod ], lowBound[ *it ] );
}
}
if ( lowBound[ nod ] == upBound[ nod ] ) {
aux.clear();
do {
k = Q.top();
Q.pop();
aux.push_back( k );
inStack[ k ] = 0;
} while ( k != nod );
aux.push_back( -1 );
sol.push_back( aux );
}
}
int main () {
freopen( "ctc.in", "r", stdin );
freopen( "ctc.out", "w", stdout );
int n, m, i, j, x, y;
scanf( "%d%d",&n,&m );
while ( m-- ) {
scanf( "%d%d",&x,&y );
v[ x ].push_back( y );
}
for ( i = 1; i <= n; ++i ) {
if ( !lowBound[ i ] ) CTC( i );
}
m = sol.size();
printf( "%d\n",m );
for ( i = 0; i < m; ++i ) {
sort ( sol[ i ].begin(), sol[ i ].end() );
for ( j = 1; j < sol[ i ].size(); ++j ) {
if ( sol[ i ][ j ] != sol[ i ][ j - 1 ] )
printf( "%d ",sol[ i ][ j ] );
}
printf( "\n" );
}
return 0;
}