Pagini recente » Cod sursa (job #3037642) | Cod sursa (job #1966366) | Cod sursa (job #1459094) | Cod sursa (job #1183230) | Cod sursa (job #699596)
Cod sursa(job #699596)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMAX 100005
#define pb push_back
int N, M, x, y, i, CTC, Stiva[NMAX];
vector< int > G[NMAX], GT[NMAX], Comp[NMAX];
bool Used[NMAX];
inline void Df1( int Nod )
{
Used[Nod] = true;
for( vector< int >::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it )
if( !Used[*it] )
Df1( *it );
Stiva[ ++Stiva[0] ] = Nod;
}
inline void Df2( int Nod )
{
Used[Nod] = true;
Comp[CTC].pb( Nod );
for( vector< int >::iterator it = GT[Nod].begin(); it != GT[Nod].end(); ++it )
if( !Used[*it] )
Df2( *it );
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &N, &M );
for( ; M--; )
{
scanf("%d%d", &x, &y );
G[x].pb( y );
GT[y].pb( x );
}
Stiva[0] = 0;
memset( Used, false, sizeof(Used) );
for( i = 1; i <= N; ++i )
if( !Used[i] )
Df1( i );
memset( Used, false, sizeof(Used) );
for( CTC = 0, i = Stiva[0]; i; --i )
if( !Used[ Stiva[i] ] )
++CTC, Df2( Stiva[i] );
printf("%d\n", CTC );
for( i = 1; i <= CTC; ++i )
{
for( vector< int >::iterator it = Comp[i].begin(); it != Comp[i].end(); ++it )
printf("%d ", *it );
printf("\n");
}
return 0;
}