Cod sursa(job #695739)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 28 februarie 2012 14:18:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
 # include <fstream>
 # include <vector>
 # define dim 200001

 using namespace std;
 
 ifstream f("biconex.in");
 ofstream g("biconex.out");

 int n , m , nr , u , st1[ dim ] , st2[ dim ] ,c[ dim ] , lv[ dim ] ;
 bool viz[ dim ] ;
 
 vector < int > a[ dim ];
 vector < int > sol[ dim ];

 void citire()
 {
    int x , y;
	f >> n >> m;
    for( int i = 1 ; i <= m ; ++i )
    {
		f >> x >> y;
        a[ x ].push_back( y );
        a[ y ].push_back( x );
    }
 }

 void add( int nod , int x )
 {
    int xx , yy ;
    nr++;
    while ( xx != nod || yy != x )
	{
        xx = st1[ u ];
        yy = st2[ u ];
        sol[ nr ].push_back( yy );
		u--;
    }
    
    sol[ nr ].push_back( xx );
 }


 void dfs( int nod, int tata )
 {
	 int x, i;
	 lv[ nod ] = lv[ tata ] + 1 ;
	 c[ nod ] = lv[ nod ];
	 viz[ nod ] = 1;
	 
	 for ( i = 0 ; i < a[ nod ].size() ; ++i )
	 {
		 x = a[ nod ][ i ];
		 if( !viz[ x ] )
		 {
			 u++;
			 st1[ u ] = nod;
			 st2[ u ] = x;
			 dfs( x , nod );
			
			 if( c[ x ] < c[ nod ] )
				 c[ nod ] = c[ x ];
			
			 if( c[ x ] >= lv[ nod ] )
				 add( nod , x );
        }
		else 
			if( x != tata && c[ x ] < c[ nod ] )
				c[ nod ] = c[ x ];
    }
 }
 
 void afiseaza()
 {
    g << nr << "\n";
    for( int i = 1 ; i <= nr ; ++i )
    {
        for ( int j = 0 ; j < sol[ i ].size() ;++j )
			g << sol[ i ][ j ] << " ";
		g << "\n";
    }
 }

 int main()
 {
	 citire();
	 dfs( 1, 0 );
	 afiseaza();
	 return 0;
 }