Cod sursa(job #2575539)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 6 martie 2020 14:12:49
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.95 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100005;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int T, N, M, x, y;
vector < int > Ad[NMAX];
int viz[NMAX], ct1;

int desc[NMAX];
int low[NMAX];

vector < int > n;

void DFS( int nod, int parent )
{
    viz[nod] = 1;

    low[nod] = desc[nod];

    for( int i = 0; i < Ad[nod].size(); ++i )
    {
        int w = Ad[nod][i];

        if( !viz[w] )
        {
            if( nod == 1 )ct1++;
            desc[w] = 1 + desc[nod];
            DFS( w, nod );
            low[nod] = min( low[nod], low[w] );
        }
        else if( w != parent )
            low[nod] = min( low[nod], desc[w] );
    }
}
void Read()
{
    fin >>
     N >> M;

    for( int i = 1; i <= M; ++i )
    {
        fin >> x >> y;
        Ad[x].push_back( y );
        Ad[y].push_back( x );
    }

    desc[1] = low[1] = 1;

    //for( int i = 1; i <= N; ++i )fout << desc[i] << ' ' << low[i] << '\n';
}

stack < int > S;
vector < int > C[NMAX];
int nrc;

void DFSc( int nod, int parent )
{
    viz[nod] = 1;

    low[nod] = desc[nod];

    for( int i = 0; i < Ad[nod].size(); ++i )
    {
        int w = Ad[nod][i];

        if( !viz[w] )
        {
            S.push( w );
            if( nod == 1 )ct1++;
            desc[w] = 1 + desc[nod];
            DFSc( w, nod );
            low[nod] = min( low[nod], low[w] );

            if( low[w] >= desc[nod] && w != parent )
            {
                S.push( nod );
                nrc++;
                while( S.size() && S.top() != w )
                {
                    C[nrc].push_back( S.top() );
                    S.pop();
                }
                if( S.size() )
                {
                C[nrc].push_back( S.top() );
                S.pop();
                }
            }
        }
        else if( w != parent )
            low[nod] = min( low[nod], desc[w] );
    }
}

void Componente()
{
    DFSc( 1, 0 );

    /*if( S.size() )nrc++;
    while( S.size() )
    {
        C[nrc].push_back( S.top() );
        S.pop();
    }*/

    fout << nrc << '\n';
    for( int i = nrc; i >= 1; --i )
    {
        //fout << C[i].size() << ' ';
        for( int j = 0; j < C[i].size(); ++j )
            fout << C[i][j] << ' ';
        fout << '\n';
    }
}
bool vn[NMAX];
void DFSn( int nod, int parent )
{
    viz[nod] = 1;

    low[nod] = desc[nod];

    for( int i = 0; i < Ad[nod].size(); ++i )
    {
        int w = Ad[nod][i];

        if( !viz[w] )
        {
            if( nod == 1 )ct1++;
            desc[w] = 1 + desc[nod];
            DFSn( w, nod );
            low[nod] = min( low[nod], low[w] );

            if( low[w] >= desc[nod] && w != parent && nod != 1 && vn[nod] == 0 )
                {n.push_back( nod ); vn[nod] = 1;}
        }
        else if( w != parent )
            low[nod] = min( low[nod], desc[w] );
    }
}

void Noduri()
{
    DFSn( 1, 0 );
    if( ct1 > 1 ) n.push_back( 1 );

    fout << n.size() << '\n';
    for( int i = n.size()-1 ; i >= 0 ; --i )
        fout << n[i] << ' ';
}

vector < pair < int, int > > m;

void DFSm( int nod, int parent )
{
    viz[nod] = 1;

    low[nod] = desc[nod];

    for( int i = 0; i < Ad[nod].size(); ++i )
    {
        int w = Ad[nod][i];

        if( !viz[w] )
        {
            desc[w] = 1 + desc[nod];
            DFSm( w, nod );
            low[nod] = min( low[nod], low[w] );

            if( low[w] > desc[nod] && w != parent )
                m.push_back( {nod, w} );
        }
        else if( w != parent )
            low[nod] = min( low[nod], desc[w] );
    }
}

void Muchii()
{
    DFSm( 1, 0 );

    fout << m.size() << '\n';
    for( int i = m.size()-1; i >= 0; --i )
        fout << m[i].first << ' ' << m[i].second << '\n';

}
void Solve()
{
    Componente();


}
int main()
{
    Read();
    Solve();
    return 0;
}