Pagini recente » Cod sursa (job #325846) | Cod sursa (job #1956427) | Cod sursa (job #419780) | Cod sursa (job #1983574) | Cod sursa (job #2668543)
#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <set>
#include <bitset>
using namespace std;
const int nMax = 100001;
vector< int > v[nMax];
int nivMin[nMax];
vector< vector< int>> componente;
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;
}
};
vector< set< int>> comp;
vector< int > dfs( int tata, int nodCurent, int nivel ) {
nivMin[ nodCurent ] = nivel;
vector< int > compActuala = { nodCurent };
for ( auto &i:v[ nodCurent ] ) {
if ( nivMin[ i ] == 0 ) {
vector< int > subComponenta = dfs( nodCurent, i, nivel + 1 );
for ( auto &j:subComponenta )
compActuala.emplace_back( j );
}
}
for ( auto &i:v[ nodCurent ] ) {
if ( i != tata && nivMin[ i ] < nivMin[ nodCurent ] )
nivMin[ nodCurent ] = nivMin[ i ];
}
if ( nivMin[ nodCurent ] == nivel ) {
if ( compActuala.size() > 1 )
// compActuala.push_back( tata );
componente.emplace_back( compActuala );
if ( tata != 0 )
componente.emplace_back( vector< int >{ tata, nodCurent } );
return vector< int >{};
}
else
return compActuala;
}
int main() {
int n, m;
FILE *fout = fopen( "biconex.out", "w" );
inputParser fin( "biconex.in" );
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 );
}
// componente.emplace_back();
dfs( 0, 1, 1 );
// componente.pop_back();
fprintf( fout, "%zu\n", componente.size() );
for ( auto &i : componente ) {
for ( auto &j:i ) {
fprintf( fout, "%d ", j );
}
fputc( '\n', fout );
}
fclose( fout );
return 0;
}