Cod sursa(job #2744485)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 24 aprilie 2021 18:58:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream f ( "biconex.in" );
ofstream g ( "biconex.out" );
const int NMAX = 100001;
vector<int>G[NMAX], CB[NMAX];
int N, M, nrCB, Niv[NMAX], Nma[NMAX], S[NMAX], vf;
bool viz[NMAX];
void citire()
{
    int x, y;
    f >> N >> M;

    for ( int i = 1; i <= M; i++ )
    {
        f >> x >> y;
        G[x].pb ( y );
        G[y].pb ( x );
    }
}
void DFS ( int x, int tata )
{
    S[++vf] = x;
    viz[x] = 1;
    Niv[x] = Niv[tata] + 1;
    Nma[x] = Niv[x];

    for ( auto &y : G[x] )
    {
        if ( y == tata )
            continue;

        if ( viz[y] )
            Nma[x] = min ( Nma[x], Niv[y] );
        else
        {
            DFS ( y, x );
            Nma[x] = min ( Nma[x], Nma[y] );

            if ( Niv[x] <= Nma[y] )
            {
                ++nrCB;

                while ( S[vf] != y )
                    CB[nrCB].pb ( S[vf--] );

                CB[nrCB].pb ( y );
                --vf;
                CB[nrCB].pb ( x );
            }
        }
    }
}
int main()
{
    citire();
    DFS ( 1, 0 );
    g << nrCB << '\n';

    for ( int i = 1; i <= nrCB; i++ )
    {
        for ( auto &x : CB[i] )
            g << x << ' ';

        g << '\n';
    }

    return 0;
}