Cod sursa(job #1013188)

Utilizator drobertDumitru Robert drobert Data 20 octombrie 2013 15:35:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#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';
	}
}