Pagini recente » Cod sursa (job #469223) | Cod sursa (job #1261053) | Cod sursa (job #1602859) | Cod sursa (job #491486) | Cod sursa (job #2251583)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
#define NMAX 100005
int NrComp, pas, Up[ NMAX ], Down[ NMAX ], InS[ NMAX ];
vector < int > V[ NMAX ];
vector < int > Sol[ NMAX ];
stack < int > Q;
void Tarjan ( int nod ) {
int i, j, fiu;
vector < int > :: iterator it;
Up[ nod ] = Down[ nod ] = ++pas;
InS[ nod ] = 1;
Q.push( nod );
for ( it = V[ nod ].begin(); it != V[ nod ].end(); ++it ) {
fiu = *it;
if ( !Up[ fiu ] ) {
Tarjan( fiu );
Down[ nod ] = min( Down[ nod ], Down[ fiu ] );
} if ( InS[ fiu ] ) {
Down[ nod ] = min( Down[ nod ], Down[ fiu ] );
}
}
if ( Up[ nod ] == Down[ nod ] ) {
++NrComp;
do {
fiu = Q.top();
Q.pop();
InS[ fiu ] = 0;
Sol[ NrComp ].push_back( fiu );
} while ( fiu != nod );
}
}
int main () {
freopen( "ctc.in", "r", stdin );
freopen( "ctc.out", "w", stdout );
int n, m, x, y, i, j, k;
scanf( "%d%d", &n, &m );
while ( m-- ) {
scanf( "%d%d", &x, &y );
V[ x ].push_back( y );
}
for ( i = 1; i <= n; ++i ) {
if ( !Up[ i ] ) {
Tarjan( i );
}
}
printf( "%d\n", NrComp );
for ( i = 1; i <= NrComp; ++i ) {
sort( Sol[ i ].begin(), Sol[ i ].end() );
for ( j = 0; j < Sol[ i ].size(); ++j ) {
printf( "%d ", Sol[ i ][ j ] );
}
printf( "\n" );
}
return 0;
}