Cod sursa(job #645006)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 7 decembrie 2011 22:59:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
 # include <fstream>
 # include <vector>
 
 # define dim 100002
 # define pb push_back
 
 using namespace std;
 
 ifstream f("ctc.in");
 ofstream g("ctc.out");
 
 int n, m;
 int viz[ dim ], ord[ dim ];
 int cr = 0, nr = 0 ;
 
 vector < int > a[ dim ], at[ dim ], d[ dim ];
 
 void dfs( int x )
 {
	int i;
	viz[ x ] = 1;
	for ( i = 0 ; i < a[ x ].size() ; i++ )
		if ( viz[ a[ x ][ i ] ] == 0 )
			dfs( a[ x ][ i ] );
		cr++;
		ord[ cr ] = x;
 }
 
 void dfst( int x )
 {
	int i;
	viz[ x ] = 0 ;
	d[ nr ].pb( x );
	for ( i = 0 ; i < at[ x ].size() ; i++ )
		if ( viz[ at[ x ][ i ] ] )
			dfst( at[ x ][ i ] );
 }
 
 void citire()
 {
	 int i, x, y;
	 
	 f >> n >> m;
	 
	 for ( i = 1 ; i <= m ; i++ )
	 {
		 f >> x >> y;
		 a[ x ].pb( y );
		 at[ y ].pb( x );
	 }
 }
 
 void afiseaza()
 {
	 int i, j;
	 /*
	 for ( i = 1 ; i <= n ; i++ )
	 {
		 for ( j = 0 ; j < a[ i ].size() ; j++ )
			 g << a[ i ][ j ] << " ";
		 g << "\n";
	 }*/
	// g << "\n";
	 for ( i = 1 ; i <= n ; i++ )
		 g << ord[ i ] << " ";
	 g << "\n";
 }
 void rezolva()
 {
	 int i;
	 for ( i = 1 ; i <= n ; i++ )
		if ( viz[ i ] == 0 )
			dfs( i );
		
		//afiseaza();
		for ( i = n ; i >= 1 ; i-- )
			if ( viz[ ord [ i ] ] )
			{
				++nr;
				dfst( ord[ i ] );
			}
 }
 
 void afisare()
 {
	 int i, j;
	 
	 g << nr << "\n";
	 
	 for ( i = 1 ; i <= nr; i++ ) 
	 {
		 for ( j = 0 ; j < d[ i ].size() ; j++ )
			 g << d[ i ][ j ] << " ";
		 g << "\n";
	 }
 }
 
 int main()
 {
	 citire();
	 rezolva();
	 afisare();
	 return 0;
 }