Pagini recente » Cod sursa (job #3161383) | Cod sursa (job #2968362) | Cod sursa (job #3242746) | Cod sursa (job #3153367) | Cod sursa (job #2672031)
#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <bitset>
using namespace std;
const int nMax = 100001;
class inputParser {
static const unsigned int buffSize = 1 << 17;
unsigned int pozBuff;
FILE *fin;
unsigned char *buffer;
void getChar( unsigned char &ch ) {
if ( pozBuff == buffSize ) {
pozBuff = 0;
assert( fread( buffer, sizeof( char ), buffSize, fin ) );
}
ch = buffer[ pozBuff++ ];
}
public:
explicit inputParser( const char *fileName ) {
fin = fopen( fileName, "r" );
assert( fin != nullptr );
buffer = new unsigned char[buffSize];
pozBuff = buffSize;
}
inputParser( const inputParser &dummy ) = delete;
inputParser &operator=( const inputParser &dummy ) = delete;
template < class intType >
inputParser &operator>>( intType &nr ) {
int sgn( 1 );
unsigned char ch;
nr = 0;
getChar( ch );
while ( isdigit( ch ) == 0 && ch != '-' )
getChar( ch );
if ( ch == '-' ) {
sgn = -1;
getChar( ch );
}
while ( isdigit( ch ) != 0 ) {
nr = nr * 10 + ch - '0';
getChar( ch );
}
nr *= sgn;
return *this;
}
inputParser &operator>>( char &ch ) {
unsigned char ch2;
do {
getChar( ch2 );
} while ( isgraph( ch2 ) == 0 );
ch = static_cast<char>(ch2);
return *this;
}
inputParser &operator>>( unsigned char &ch ) {
getChar( ch );
do {
getChar( ch );
} while ( isgraph( ch ) == 0 );
return *this;
}
~inputParser() {
fclose( fin );
delete[] buffer;
}
};
class outputParser {
static const unsigned int buffSize = 1 << 17;
unsigned int pozBuff;
FILE *fout;
unsigned char *buffer;
void putChar( const unsigned char ch ) {
if ( pozBuff == buffSize ) {
pozBuff = 0;
fwrite( buffer, sizeof( char ), buffSize, fout );
}
buffer[ pozBuff++ ] = ch;
}
public:
explicit outputParser( const char *fileName ) {
fout = fopen( fileName, "w" );
buffer = new unsigned char[buffSize];
pozBuff = 0;
}
outputParser( const outputParser &dummy ) = delete;
outputParser &operator=( const outputParser &dummy ) = delete;
template < class intType >
outputParser &operator<<( intType nr ) {
if ( nr < 0 ) {
putChar( '-' );
nr = -nr;
}
int cif[20];
int pozCif = 0;
do {
cif[ pozCif++ ] = nr % 10;
nr /= 10;
} while ( nr > 0 );
while ( pozCif > 0 ) {
unsigned char ch = cif[ --pozCif ] + '0';
putChar( ch );
}
return *this;
}
outputParser &operator<<( char ch ) {
putChar( ch );
return *this;
}
outputParser &operator<<( unsigned char ch ) {
putChar( ch );
return *this;
}
~outputParser() {
fwrite( buffer, sizeof( char ), pozBuff, fout );
delete[] buffer;
fclose( fout );
}
};
/*
vector< vector< int>> compActuala;
vector< int > subComponenta;
vector< int > dfs( int tata, int nodCurent, int nivel ) {
niv[ nodCurent ] = nivMin[ nodCurent ] = nivel;
compActuala.emplace_back( vector< int >{ nodCurent } );
//vector< int > compActuala = { nodCurent };
for ( auto &i:v[ nodCurent ] ) {
if ( i != tata ) {
if ( niv[ i ] == 0 ) {
subComponenta = dfs( nodCurent, i, nivel + 1 );
// compActuala[ compActuala.size() - 1 ].insert( compActuala[ compActuala.size() - 1 ].end(),
// subComponenta.begin(), subComponenta.end() );
for ( auto &j:subComponenta ) {
compActuala[ compActuala.size() - 1 ].emplace_back( j );
}
}
if ( niv[ i ] < niv[ nodCurent ] ) {
if ( niv[ i ] < nivMin[ nodCurent ] )
nivMin[ nodCurent ] = niv[ i ];
}
else {
if ( nivMin[ i ] < nivMin[ nodCurent ] )
nivMin[ nodCurent ] = nivMin[ i ];
}
}
}
if ( nivMin[ nodCurent ] >= nivel - 1 ) {
if ( nivMin[ nodCurent ] == nivel - 1 )
compActuala[ compActuala.size() - 1 ].push_back( tata );
if ( tata > 0 && compActuala[ compActuala.size() - 1 ].size() == 1 )
compActuala[ compActuala.size() - 1 ].push_back( tata );
if ( compActuala[ compActuala.size() - 1 ].size() > 1 )
componente.emplace_back( compActuala[ compActuala.size() - 1 ] );
compActuala.pop_back();
return vector< int >{};
}
else {
vector< int > aux = compActuala[ compActuala.size() - 1 ];
compActuala.pop_back();
return aux;
}
}
*/
int hmin[nMax];
vector< int > v[nMax];
vector< int > tree[nMax];
int coParinti, coMuchii;
int p[nMax];
inputParser fin( "biconex.in" );
outputParser fout( "biconex.out" );
bitset< nMax > vizitat;
vector< int > compTataFiu;
void dfs( int nod, int nivel, int tata ) {
hmin[ nod ] = nivel;
for ( auto &i : v[ nod ] ) {
if ( i != tata ) {
if ( hmin[ i ] == 0 ) {
dfs( i, nivel + 1, nod );
if ( hmin[ i ] <= nivel ) {
coMuchii++;
tree[ i ].push_back( nod );
tree[ nod ].push_back( i );
}
else {
p[ i ] = nod;
if ( tree[ i ].size() == 0 ) {
coParinti++;
vizitat[ i ] = true;
}
compTataFiu.push_back( i );
}
}
hmin[ nod ] = min( hmin[ nod ], hmin[ i ] );
}
}
}
void biconex( int nod ) {
vizitat[ nod ] = true;
fout << nod << ' ';
for ( auto &i:tree[ nod ] ) { ///ce face parte din componenta actuala
if ( !vizitat[ i ] )
biconex( i );
}
}
int main() {
int n, m;
fin >> n >> m;
for ( int i = 0; i < m; i++ ) {
int a, b;
fin >> a >> b;
v[ a ].push_back( b );
v[ b ].push_back( a );
}
dfs( 1, 1, 0 );
fout << ( n - 1 ) - coMuchii + 1 + coParinti << '\n';
for ( int i = 1; i <= n; i++ ) {
if ( !vizitat[ i ] ) {
//biconex( i, 1, 0 );
biconex( i );
fout << '\n';
}
}
for ( auto &i:compTataFiu ) {
fout << i << ' ' << p[ i ] << '\n';
}
return 0;
}