Cod sursa(job #2781392)

Utilizator ionut31Ioan Ionescu ionut31 Data 9 octombrie 2021 13:09:37
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int vizitat[100005];
int nivel[100005]; //vector ce retine nivelul la care se afla fiecare nod in graful de parcurgere DFS
int nma[100005]; //vector ce retine nivelul minim accesibil(nivelul minim al unui ascendent la care are acces printr-o muchie
                // de intoarcere) de catre fiecare nod
stack<int> stiva; //stiva in care vom retine nodurile grafului in ordinea parcurgerii DFS
vector<vector<int>> biconexe; //vectorul de componente biconexe


int n, m;

//liste de adiacente
vector<vector<int>> la;

//determinare componente biconexe
void bcx(int tata)
{

    vector<int> componenta;
    while(!stiva.empty() && stiva.top()!=tata)
    {
        componenta.push_back(stiva.top());
        stiva.pop();
    }
    componenta.push_back(tata);
    biconexe.push_back(componenta);
}

//parcurgere dfs
void dfs(int x, int tata)
{
    vizitat[x] = 1;
    nivel[x] = nivel[tata] + 1;
    nma[x] = nivel[x]; //initiaizez nma cu nivelul curent(nu stiu momentan pana la ce nivel se poate intoarce)
    stiva.push(x); //adaug nodul in stiva
    //fout << x << " ";

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int y = la[x][i];
        if (vizitat[y] == 0)
        {
            dfs(y, x);

            //daca y, care este fiu al lui x poate sa se intoarca mai sus decat x, actualizez nma[x]
            // (x prin intermediul lui se va intoarce mai sus)
            if(nma[x] > nma[y])
                nma[x] = nma[y];


            //determinare componente biconexe
            if(nivel[x] <= nma[y])
                bcx(x);

        }
        else //am dat de o muchie de intoarcere
        {
            //daca y, care este fiu al lui x se afla mai sus decat x(a fost deja vizitat) si nivelul sau este
            // strict mai mic(e mai sus) decat nivelul la care se poate intoarce x, atunci actualizez nma[x]
            // (x prin intermediul lui y, al muchiei de inoarcere, se va intoarce mai sus)
            if(nma[x] > nivel[y])
                nma[x] = nivel[y];
        }
    }
}


int main()
{
    fin>>n>>m;
    la.resize(n+1);
    for(int i=0; i<m; ++i)
    {
        int x ,y;
        fin >> x >> y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

    dfs(1, 1);

    fout << biconexe.size() << "\n";

    for(int i=0; i<biconexe.size(); ++i)
    {
        for(int j=0; j<biconexe[i].size(); ++j)
            fout << biconexe[i][j] << " ";
        fout << "\n";
    }
}