Cod sursa(job #806827)

Utilizator MtkMarianHagrSnaf MtkMarian Data 3 noiembrie 2012 16:28:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std ;
#define NMAX 100005

vector < int > list[ NMAX ] ;
vector < vector <  int  > > comp_biconex ;
stack <  pair < int , int > > s ;

int n , m , x , y , index = 1 , dindex[NMAX]={0} , lowpoint [ NMAX] ;


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

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

}
void articulatie ( int v ,int vsucc )
{
	int x = 0 , y = 0;
	vector < int > afis ;
	vector< int > :: iterator it ;
	do
	{
		x = s.top().first ;
		y = s.top().second ;
		s.pop ( ) ;
		afis.push_back( x ) , afis.push_back( y ) ;
	}
	while( x!=v || y!=vsucc ) ;

	
	comp_biconex.push_back( afis );


}
void biconex( int v )
{
	dindex[ v ] = index ;
	lowpoint[ v ] = index ;
	++index;

	vector< int > :: iterator it ;

	for ( it = list [v].begin() ; it != list [ v ].end() ; ++it )
	{
		
		if ( !dindex [ *it ] )
		{
			s.push( make_pair( v , *it ) ) ;
			biconex ( *it );
			lowpoint [ v ] = min (lowpoint[ v ] , lowpoint[ *it ] ) ;

			if ( lowpoint [ *it  ] >= dindex [ v ] )  articulatie (  v , *it ) ;
			
		}
		else 
		{
			lowpoint[ v  ] = min (lowpoint[ v ] , dindex[ *it ]  );
		}
	}
}		
void scrie( )
{
	printf("%d\n", comp_biconex.size( ) );

	vector< int > afis;
	vector< int > :: iterator it ;

	for( int i = 0 ;  i < comp_biconex.size() ; ++i )
	{
		afis=comp_biconex [ i ];
		

		sort(afis.begin() , afis.end() );
		
		it=unique( afis.begin() , afis.end() );

		afis.resize( it - afis.begin( ) ) ; 
			
		for( int j = 0 ; j < afis.size() ; ++j )
			printf("%d " ,afis[ j ] );

		printf("\n");
		afis.clear();
	}
	
}

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

	citeste() ;
	biconex( 1 ) ;
	scrie() ;
	return 0;
}