Cod sursa(job #852912)
#include <cstdio>
#include <cstdlib>
#include <vector>
#define nmax 10000
using namespace std ;
int stiva [ nmax ] , aaa ;
int N , M , stiva_nr , nr_componente ;
vector<int> vecini [ nmax ] , biconexe [ nmax ] ;
int t [ nmax ] , niv [ nmax ] , l [ nmax ] ;
bool valid [ nmax ] ;
void citire ()
{
FILE *fin ;
fin = fopen ( "biconex.in" , "rt" ) ;
fscanf ( fin , "%d %d" , &N , &M ) ;
for ( int i = 1 ; i <= M ; i++ )
{
int a , b ;
fscanf ( fin , "%d %d" , &a , &b ) ;
vecini [ a ].push_back ( b ) ;
vecini [ b ].push_back ( a ) ;
}
l [ 1 ] = 1 ;
t [ 1 ] = 0 ;
niv [ 1 ] = 1 ;
for ( int i = 1 ; i <= N ; i++ )
valid [ i ] = 1 ;
}
void stiva_adauga ( int aaa )
{
stiva_nr++ ;
stiva [ stiva_nr ] = aaa ;
}
void gasit_componenta ( int nod )
{
nr_componente++ ;
while ( stiva [ stiva_nr ] != nod )
{
biconexe[ nr_componente ].push_back ( stiva [ stiva_nr ] ) ;
stiva_nr-- ;
}
biconexe[ nr_componente ].push_back ( stiva [ stiva_nr ] ) ;
}
void dfs ( int nod )
{
valid [ nod ] = 0 ;
stiva_adauga ( nod ) ;
for ( int i = 0 ; i < vecini [ nod ].size () ; i++ )
{
int y = vecini [ nod ][ i ] ;
if ( !valid [ y ] )
{
if ( y < t [ nod ] )
{
l [ nod ] = niv [ y ] ;
}
continue ;
}
t [ y ] = nod ;
niv [ y ] = niv [ nod ] + 1 ;
l [ y ] = niv [ y ] ;
dfs ( y ) ;
if ( l [ nod ] > l [ y ] ) l [ nod ] = l [ y ] ;
if ( l [ y ] >= niv [ t [ y ] ] ) gasit_componenta ( t [ y ] ) ;
}
}
int main ()
{
citire () ;
for ( int i = 1 ; i <= N ; i++ )
if ( valid [ i ] )
{
niv [ i ] = 1 ;
dfs ( i ) ;
}
FILE *fout ;
fout = fopen ( "biconex.out" , "wt" ) ;
fprintf ( fout , "%d\n" , nr_componente ) ;
for ( int i = 1 ; i <= nr_componente ; i++ )
{
for ( int j = biconexe [ i ].size () - 1 ; j >= 0 ; j-- )
fprintf ( fout , "%d " , biconexe[ i ][j] ) ;
fprintf ( fout , "\n" ) ;
}
return 0 ;
}