Cod sursa(job #2672031)

Utilizator ReksioCroftOctavian Florin Staicu ReksioCroft Data 12 noiembrie 2020 22:39:13
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.68 kb
#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;
}