Pagini recente » Cod sursa (job #890912) | Cod sursa (job #2347861) | Cod sursa (job #1926870) | Cod sursa (job #467148) | Cod sursa (job #1725603)
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 100005
#define INFI 0x3f3f3f
stack < int > Q;
vector < int > aux;
vector < int > v[ NMAX ];
vector < vector < int > > sol;
int pas;
int upBound[ NMAX ];
int in_stack[ NMAX ];
int lowBound[ 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( !upBound[ i ] ) tarjan( i );
s = sol.size();
printf("%d\n",s);
for( i = 0; i < s; ++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, t, fiu;
upBound[ nod ] = lowBound[ nod ] = ++pas;
Q.push( nod );
in_stack[ nod ] = 1;
for( int fiu : v[ nod ] ){
if( !lowBound[ fiu ] ){
tarjan( fiu );
lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
}
else if( in_stack[ fiu ] )
lowBound[ nod ] = minim( lowBound[ nod ], lowBound[ fiu ] );
}
if( lowBound[ nod ] == upBound[ nod ] ){
aux.clear();
do{
aux.push_back( t = Q.top() );
in_stack[ t ] = 0;
Q.pop();
}while( t != nod );
sol.push_back( aux );
}
}
int minim( int a, int b ){
if( a > b ) return b;
return a;
}