Cod sursa(job #2791775)

Utilizator XeinIonel-Alexandru Culea Xein Data 31 octombrie 2021 00:08:18
Problema Componente biconexe Scor 54
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 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 nivelInArbDFS[NMAX];  // folosit si ca vizitat[]
int nivelMinVecini[NMAX];

void Dfs(int nod, int parinte)
{
    nivelInArbDFS[nod] = nivelInArbDFS[parinte] + 1;
    nivelMinVecini[nod] = NMAX;
    for (int& vecin : Adiacenta[nod])
    {
        if (nivelInArbDFS[vecin])  // daca e vizitat
        {
            if (nivelMinVecini[nod] > nivelInArbDFS[vecin] && vecin != parinte)
                nivelMinVecini[nod] = nivelInArbDFS[vecin];
        }
        else
        {
            Stiva[++stVf] = {nod, vecin};
            Dfs(vecin, nod);

            if (nivelMinVecini[nod] > nivelMinVecini[vecin])
                nivelMinVecini[nod] = nivelMinVecini[vecin];
            
            if (nivelMinVecini[vecin] >= nivelInArbDFS[nod])
            {
                compBic.push_back( {Stiva[stVf].second} );
                while (Stiva[stVf].first != nod)
                    compBic.back().push_back(Stiva[stVf--].first);
                compBic.back().push_back(Stiva[stVf--].first);
            }
        }

    }
}

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);
    }

    nivelInArbDFS[1] = 1;
    Dfs(1, 0);

    g << compBic.size() << '\n';
    for (auto& comp : compBic)
    {
        for (int& nod : comp)
            g << nod << ' ';
        g << '\n';
    }

    return 0;
}