Cod sursa(job #2368806)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 5 martie 2019 18:09:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100005;

int N, M;
vector <int> Ad[NMAX];

stack <int> S;

int disc[NMAX];
int low[NMAX];
int t;
int nr_comp;
bool viz[NMAX];

vector <int> Comp[NMAX];

void read()
{
    fin >> N >> M;

    int i, x, y;

    for ( i = 1; i <= M; ++i )
    {
        fin >> x >> y;

        Ad[x].push_back( y );
        Ad[y].push_back( x );
    }

    fin.close();
}

void DFS( int nod, int parent )
{
    disc[nod] = low[nod] = ++t;

    int i, w;

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

        if ( w == parent ) continue;

        if ( !disc[w] )
        {
            S.push( w );

            DFS( w, nod );

            low[nod] = min( low[nod], low[w] );

            if ( low[w] >= disc[nod] )
            {
                ++nr_comp;

                S.push( nod );

                while ( !S.empty() && S.top() != w )
                {
                    Comp[nr_comp].push_back( S.top() );
                    S.pop();
                }

                if ( !S.empty() )
                {
                    Comp[nr_comp].push_back( S.top() );
                    S.pop();
                }
            }
        }
        else if ( w != parent )
                 low[nod] = min( low[nod], disc[w] );
    }
}

void solve()
{
    int i, j;

    DFS( 1, 0 );

    fout << nr_comp << '\n';

    for ( i = 1; i <= nr_comp; ++i )
    {
        for ( j = 0; j < Comp[i].size(); ++j )
             fout << Comp[i][j] << ' ';

        fout << '\n';
    }

}

int main()
{
    read();
    solve();

    fout.close();

    return 0;
}