Cod sursa(job #2583279)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 17 martie 2020 23:18:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

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

const int NMax = 1e5;

int N, M, NrC, Lev[NMax + 5], MinLev[NMax + 5];
bool A[NMax + 5], Use[NMax + 5];

vector <int> G[NMax + 5], Sol[NMax + 5];
stack <pair<int, int> > S;

void Process(int Nod)
{
    int topX, topY;
    ++NrC;

    do
    {
        topX = S.top().first, topY = S.top().second;
        Sol[NrC].push_back(topY);
        S.pop();
    }
    while(!S.empty() && topX != Nod && topY != Nod);

    Sol[NrC].push_back(topX);
}

void DFS(int Nod, int Tata)
{
    int nrSons = 0; Use[Nod] = 1;
    Lev[Nod] = MinLev[Nod] = Lev[Tata] + 1;

    for(auto Vecin : G[Nod])
    {
        if(!Use[Vecin])
        {
            S.push({Nod, Vecin});
            DFS(Vecin, Nod);
            MinLev[Nod] = min(MinLev[Nod], MinLev[Vecin]), nrSons++;

            if(MinLev[Vecin] >= Lev[Nod])
                Process(Nod);
        }
        else
            MinLev[Nod] = min(MinLev[Nod], Lev[Vecin]);
    }
}

int main()
{
    fin >> N >> M;

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

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

    for(int i = 1; i <= N; i++)
        if(Use[i] == 0)
            DFS(i, 0);

    fout << NrC << '\n';

    for(int i = 1; i <= NrC; i++)
    {
        for(auto x : Sol[i])
            fout << x << " ";
        fout << '\n';
    }
    fin.close();
    fout.close();

    return 0;
}