Pagini recente » Cod sursa (job #436068) | Cod sursa (job #366002) | Cod sursa (job #1614392) | Cod sursa (job #88246) | Cod sursa (job #1911227)
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
#define NMAX 100001
int LowBound[ NMAX ];
int UpBound[ NMAX ];
int inS[ NMAX ];
int pas;
stack < int > S;
vector < int > aux;
vector < int > V[ NMAX ];
vector < vector < int > > Sol;
void Tarjan ( int nod ) {
int i, j, t, fiu;
vector < int > :: iterator it;
LowBound[ nod ] = UpBound[ nod ] = ++pas;
S.push( nod ); inS[ nod ] = 1;
for ( it = V[ nod ].begin(); it != V[ nod ].end(); ++it ) {
fiu = *it;
if ( !LowBound[ fiu ] ) {
Tarjan( fiu );
LowBound[ nod ] = min( LowBound[ nod ], LowBound[ fiu ] );
} else if ( inS[ nod ] ) {
LowBound[ nod ] = min( LowBound[ nod ], LowBound[ fiu ] );
}
}
if ( LowBound[ nod ] == UpBound[ nod ] ) {
aux.clear();
do {
aux.push_back( t = S.top() );
inS[ t ] = 0;
S.pop();
} while ( t != nod );
Sol.push_back( aux );
}
}
int main () {
freopen( "ctc.in", "r", stdin );
freopen( "ctc.out", "w", stdout );
int n, m, i, j, x, y, d;
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 ] ) Tarjan( i );
}
printf( "%d\n",Sol.size() );
for ( i = 0; i < Sol.size(); ++i ) {
sort( Sol[ i ].begin(), Sol[ i ].end() );
x = -1;
for ( j = 0; j < Sol[ i ].size(); ++j ) {
if ( x != Sol[ i ][ j ] ) {
printf( "%d ", Sol[ i ][ j ] );
x = Sol[ i ][ j ];
}
}
printf( "\n" );
}
return 0;
}