Pagini recente » Solutii preONI 2006 - Runda 1 | Cod sursa (job #1729626) | Cod sursa (job #1268846) | Cod sursa (job #1540490) | Cod sursa (job #2255926)
#include <cstdio>
#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
#define NMAX 100005
int nr, pas, U[ NMAX ], D[ NMAX ], InStack[ NMAX ];
stack < int > Q;
vector < int > V[ NMAX ], S[ NMAX ];
void tarjan( int nod ) {
int i, fiu;
vector < int > :: iterator it;
Q.push( nod );
InStack[ nod ] = 1;
U[ nod ] = D[ nod ] = ++pas;
for ( it = V[ nod ].begin(); it != V[ nod ].end(); ++it ) {
fiu = *it;
if ( U[ fiu ] == 0 ) {
tarjan( fiu );
D[ nod ] = min( D[ nod ], D[ fiu ] );
} else if ( InStack[ fiu ] ) {
D[ nod ] = min( D[ nod ], D[ fiu ] );
}
}
if ( U[ nod ] == D[ nod ] ) {
nr++;
do {
S[ nr ].push_back( fiu = Q.top() );
Q.pop();
InStack[ fiu ] = 0;
} while ( fiu != nod );
}
}
int main () {
freopen( "ctc.in", "r", stdin );
freopen( "ctc.out", "w", stdout );
int n, m, i, j, x, y, nod, fiu;
scanf( "%d%d", &n,&m );
while ( m-- ) {
scanf( "%d%d", &x,&y );
V[ x ].push_back( y );
}
for ( i = 1; i <= n; ++i ) {
if ( U[ i ] == 0 ) tarjan( i );
}
printf( "%d\n",nr );
for ( i = 1; i <= nr; ++i ) {
sort( S[ i ].begin(), S[ i ].end() );
for ( j = 0; j < S[ i ].size(); ++j ) {
printf( "%d ", S[ i ][ j ] );
}
printf( "\n" );
}
return 0;
}