Cod sursa(job #806235)

Utilizator MtkMarianHagrSnaf MtkMarian Data 2 noiembrie 2012 09:46:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include<cstdio>
#include<algorithm>
#include<iterator>
#include<stack>
#include<vector>

using namespace std ;
#define NMAX 100005


vector <int> list [ NMAX ] , afis ;
stack < int > s;
vector < vector < int > > ctc;

int n , m , x , y , index[NMAX]={ 0 } , lowlink[NMAX] , ind = 1 , in_stiva[NMAX]= { 0 };

void citeste()
{
	
	scanf (  "%d%d", &n , &m) ;

	for  ( int i = 1  ; i <= m  ; ++i )
	{
		scanf("%d%d", &x ,&y ) ;
		list[x].push_back( y ) ;

	}
	



}
inline int min(int a , int b )
{
	return a <= b ? a : b ;
}
void scrie(vector< vector < int> > comp_t_con)
{
	printf("%d\n", comp_t_con.size( ) );

	vector< int > afis;
	vector< int > :: iterator it ;
	for( int i = 0 ;  i < comp_t_con.size() ; ++i )
	{
		afis=comp_t_con [ i ];
		for( it = afis .begin() ; it < afis.end() ; ++it )
			printf("%d " ,*it);
			printf("\n");
	}
	
}

void tarjan( int v  )
{
	index[ v ] = ind ;
	lowlink [ v ] = ind ;
	++ind;
	s.push( v ) ;
	in_stiva[ v ] = 1;
	vector < int > ::const_iterator it ;

	for( it = list[ v ].begin() ; it <list[ v ].end() ; ++it )
	{
		if ( ! index [ *it ] )
		{
			tarjan( *it  );
			lowlink [ v ] = min ( lowlink[ v ] , lowlink [ *it ] ) ;
		}
		else
			if ( in_stiva [ *it ] )
			{
				lowlink [ v ]  = min ( lowlink[v] , index[ *it ] ) ;

			}
	}
	if( lowlink [ v ] == index [ v ] )
	{
		int aux ;
		afis.clear( );
		do
		{
			afis.push_back (aux= s.top() );
			in_stiva[ aux ] = 0;
			s.pop();
			

			
		}while( v != aux );
		ctc.push_back( afis );
		


	}


	

}

int main( )
{
	freopen( "ctc.in" , "r" , stdin ) ;
	freopen( "ctc.out" , "w" , stdout ) ;

	citeste();

	for( int i = 1 ; i <= n ; ++i   )
	{
		if ( !index[ i ] )
		tarjan( i );
	}
	scrie( ctc);

	return  0 ;
}