Pagini recente » Cod sursa (job #933938) | Cod sursa (job #2833310) | Cod sursa (job #2822860) | Cod sursa (job #2343353) | Cod sursa (job #1013188)
#include <fstream>
using namespace std;
ifstream cin( "ctc.in" );
ofstream cout( "ctc.out" );
int n, m, x, y, viz[ 100001 ];
int *compCon[ 100001 ], *gt[ 100001 ], *g[ 100001 ];
int postOrd[ 100001 ], nrCompCon;;
void dfs( int k )
{
int i;
viz[ k ] = 1;
for ( i = 1; i <= g[ k ][ 0 ]; i++ )
if ( !viz[ g[ k ][ i ] ] )
dfs( g[ k ][ i ] );
postOrd[ ++postOrd[ 0 ] ] = k;
}
void dfsT( int k )
{
int i;
viz[ k ] = 0;
compCon[ nrCompCon ][ 0 ]++;
compCon[ nrCompCon ] = ( int * ) realloc( compCon[ nrCompCon ], ( compCon[ nrCompCon ][ 0 ] + 1 ) * sizeof( int ) );
compCon[ nrCompCon ][ compCon[ nrCompCon ][ 0 ] ] = k;
for ( i = 1; i <= gt[ k ][ 0 ]; i++ )
if ( viz[ gt[ k ][ i ] ] )
dfsT( gt[ k ][ i ] );
}
int main ()
{
int i, j;
cin >> n >> m;
for ( i = 1; i <= n ;i++ )
{
g[ i ] = ( int * ) realloc( g[ i ],sizeof( int ) );
g[ i ][ 0 ] = 0;
gt[ i ] = ( int * ) realloc( gt[ i ],sizeof( int ) );
gt[ i ][ 0 ] = 0;
}
for ( i = 1; i <= m; i++ )
{
cin >> x >> y;
g[ x ][ 0 ]++;
g[ x ] = ( int * ) realloc( g[ x ],( g[ x ][ 0 ] + 1 ) * sizeof( int ) );
g[ x ][ g[ x ][ 0 ] ] = y;
gt[ y ][ 0 ]++;
gt[ y ] = ( int * ) realloc( gt[ y ],( gt[ y ][ 0 ] + 1 ) * sizeof( int ) );
gt[ y ][ gt[ y ][ 0 ] ] = x;
}
for ( i = 1; i <= n; i++ )
if ( !viz[ i ] )
dfs( i );
for ( i = n; i > 0; i-- )
if ( viz[ postOrd[ i ] ] )
{
nrCompCon++;
compCon[ nrCompCon ] = ( int * ) realloc( compCon[ nrCompCon ], sizeof( int ) );
compCon[ nrCompCon ][ 0 ] = 0;
dfsT( postOrd[ i ] );
}
cout << nrCompCon << '\n';
for ( i = 1; i <= nrCompCon; i++ )
{
for ( j = 1; j <= compCon[ i ][ 0 ]; j++ )
cout << compCon[ i ][ j ] << " ";
cout << '\n';
}
}