Cod sursa(job #2790438)

Utilizator XeinIonel-Alexandru Culea Xein Data 28 octombrie 2021 23:24:12
Problema Componente biconexe Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <vector>
#include <utility>

#define NMAX 100009

std::vector<int> Adiacenta[NMAX];
std::vector< std::vector<int> > compBic;
std::pair<int, int> Stiva[NMAX * 2];
int stVf;
int NrComp;
int nivelInArbDFS[NMAX];
int nivelMinVecini[NMAX];
bool vizitat[NMAX];


void Dfs(int nod)
{
    vizitat[nod] = true;
    nivelMinVecini[nod] = NMAX;
    for (int vecin : Adiacenta[nod])
    {
        if (!vizitat[vecin])
        {
            Stiva[++stVf] = {nod, vecin};
            nivelInArbDFS[vecin] = nivelInArbDFS[nod] + 1;
            Dfs(vecin);
        }
        if (nivelInArbDFS[vecin] < nivelMinVecini[nod])
            nivelMinVecini[nod] = nivelInArbDFS[vecin];
    }
}

int main()
{
    std::ifstream f("biconex.in");
    std::ofstream g("biconex.out");
    int N, M;

    f >> N >> M;
    for (int x, y, i = 0; i < M; ++i)
    {
        f >> x >> y;
        Adiacenta[x].push_back(y);
        Adiacenta[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i)
        if (!vizitat[i])
        {
            stVf = 0;
            nivelInArbDFS[i] = 1;
            Dfs(i);

            if (stVf == 0)
            {
                ++NrComp;
                compBic.push_back({i});
            }
            else
                while (stVf)
                {
                    ++NrComp;
                    int nod = Stiva[stVf].second;
                    compBic.push_back({nod});
                    int idx = compBic.size() - 1;
                    while (stVf && nivelInArbDFS[ Stiva[stVf].first ] > nivelMinVecini[nod])
                    {
                        compBic[idx].push_back( Stiva[stVf].first );
                        --stVf;
                    }
                    compBic[idx].push_back( Stiva[stVf].first );
                    --stVf;
                }     
        }

    g << NrComp << '\n';
    for (int i = 0; i < compBic.size(); ++i)
    {
        for(int j = 0; j < compBic[i].size(); ++j)
            g << compBic[i][j] << ' ';
        g << '\n';
    }

    return 0;
}