Pagini recente » Cod sursa (job #1399288) | Cod sursa (job #2726514) | Cod sursa (job #343425) | Cod sursa (job #428623) | Cod sursa (job #695739)
Cod sursa(job #695739)
# 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;
}