Pagini recente » Cod sursa (job #3040303) | Cod sursa (job #1273404) | Cod sursa (job #1463232) | Cod sursa (job #566937) | Cod sursa (job #591790)
Cod sursa(job #591790)
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 100001
#define pb push_back
using namespace std;
vector< int > G1[NMAX], G2[NMAX], New, CTC[NMAX];
int N, M, i, x, y, Stack[NMAX], NrCTC;
bool USED[NMAX];
inline void DF( int Nod )
{
USED[Nod] = true;
for( vector< int >::iterator it = G1[Nod].begin(); it != G1[Nod].end(); it++ )
if( !USED[*it] )
DF( *it );
Stack[ ++ Stack[0] ] = Nod;
}
inline void DFCTC( int Nod )
{
USED[Nod] = false;
CTC[NrCTC].pb( Nod );
for( vector< int >::iterator it = G2[Nod].begin(); it != G2[Nod].end(); it++ )
if( USED[*it] )
DFCTC( *it );
}
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
in >> N >> M;
while( M-- )
{
in >> x >> y;
G1[x].pb( y );
G2[y].pb( x );
}
memset( USED, false, sizeof(USED) );
Stack[0] = 0;
for( i = 1; i <= N; i++ )
if( !USED[i] )
DF( i );
NrCTC = 0;
for( i = N; i; i-- )
if( USED[ Stack[i] ] )
{
DFCTC( Stack[i] );
++NrCTC;
}
out << NrCTC << '\n';
for( int it = 0; it < NrCTC; it++ )
{
for( int it2 = 0; it2 < (int)CTC[it].size(); it2++ )
out << CTC[it][it2] << ' ';
out << '\n';
}
return 0;
}