Pagini recente » Cod sursa (job #2671461) | Cod sursa (job #1604196) | Cod sursa (job #1023719) | Cod sursa (job #1091323) | Cod sursa (job #1725406)
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 100005
#define INFI 0x3f3f3f3
stack < int > Q;
vector < int > aux;
vector < int > v[ NMAX ];
vector < vector <int > > sol;
int pas;
int vizt[ NMAX ];
int lowBound[ NMAX ];
int upBound[ NMAX ];
int in_stack[ NMAX ];
void tarjan( int nod );
int minim( int a, int b );
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n, m, i, j, x, y, s, t, 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( !vizt[ i ] ) tarjan( i );
printf("%d\n",sol.size());
for( i = 0; i < sol.size(); ++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;
}
void tarjan( int nod ){
int i, j, ok, fiu;
Q.push( nod );
vizt[ nod ] = in_stack[ nod ] = 1;
lowBound[ nod ] = upBound[ nod ] = ++pas;
for( i = 0; i < v[ nod ].size(); ++i ){
fiu = v[ nod ][ i ];
if( !vizt[ fiu ] ){
tarjan( fiu );
lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
}
else if( in_stack[ v[ nod ][ i ] ] )
lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
}
if( lowBound[ nod ] == upBound[ nod ] ){
ok = 0;
aux.clear();
while( !ok ){
aux.push_back( Q.top() );
in_stack[ Q.top() ] = 0;
ok = ( nod == Q.top() );
Q.pop();
}
sol.push_back( aux );
}
}
int minim( int a, int b ){
if( a > b ) return b;
return a;
}