Pagini recente » Cod sursa (job #1437121) | Cod sursa (job #2029696) | Cod sursa (job #1323757) | Cod sursa (job #2982889) | Cod sursa (job #383848)
Cod sursa(job #383848)
#include<stdio.h>
#include<vector>
#include<deque>
using namespace std;
#define NMAX 100004
vector< int >G[NMAX];
int UPP[NMAX],DOWN[NMAX];
deque< int >S;
bool viz[NMAX],in_S[NMAX];
int ANS,index;
vector< int >SOL[NMAX];
//Decebal's fist
void traian( int nod )
{
++index;
UPP[ nod ]=index;
DOWN[ nod ]=index;
S.push_back( nod );
in_S[nod]=1;
for( vector< int >::iterator it=G[nod].begin(); it!=G[nod].end(); ++it )
{
if( !UPP[ *it ] )
{
traian( *it );
DOWN[ nod ]=min( DOWN[ nod ], DOWN[*it] );
}
else
{
if( in_S[ *it ] )
DOWN[ nod ]=min( DOWN[ nod ], DOWN[ *it ] );
}
}
if( UPP[ nod ]==DOWN[ nod ] )
{
++ANS;
int node;
do{
node=S.back();
S.pop_back();
in_S[node]=0;
SOL[ANS].push_back( node );
}while( node!=nod );
}
}
void show()
{
printf("%d\n",ANS);
int i;
for(i=1; i<=ANS; ++i)
{
for( vector< int >::iterator it=SOL[i].begin(); it!=SOL[i].end(); ++it )
printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int N,M;
scanf("%d%d",&N,&M);
int i,a1,a2;
for(i=1; i<=M; ++i)
{
scanf("%d%d",&a1,&a2);
G[a1].push_back(a2);
}
for(i=1; i<=N; ++i)
if( !UPP[i] )
traian( i );
show();
return 0;
}