Pagini recente » Cod sursa (job #1332718) | Cod sursa (job #2105500) | Cod sursa (job #120867) | Cod sursa (job #2059445) | Cod sursa (job #806827)
Cod sursa(job #806827)
#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;
}