Cod sursa(job #3188117)

Utilizator SSKMFSS KMF SSKMF Data 1 ianuarie 2024 19:04:53
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin ("biconex.in");
ofstream cout ("biconex.out");

vector <int> adiacenta[100001];
vector < vector <int> > componente;
int vizitat[100001] , minim_accesibil[100001] , moment[100001];
bool in_stiva[100001];

void Parcurgere (const int nod_actual , const int nod_sursa)
{
    in_stiva[nod_actual] = true;
    vizitat[++vizitat[0]] = nod_actual;
    minim_accesibil[nod_actual] = moment[nod_actual] = ++moment[0];
    for (auto nod_vecin : adiacenta[nod_actual]) {
        if (nod_vecin != nod_sursa) {
            if (in_stiva[nod_vecin]) 
                { minim_accesibil[nod_actual] = min(minim_accesibil[nod_actual] , moment[nod_vecin]); }
            else if (!moment[nod_vecin])
            { 
                Parcurgere(nod_vecin , nod_actual);

                if (minim_accesibil[nod_vecin] < minim_accesibil[nod_actual])
                    { minim_accesibil[nod_actual] = minim_accesibil[nod_vecin]; }
                else
                {
                    const int indice = componente.size();
                    componente.resize(indice + 1);

                    while (in_stiva[nod_vecin]) {
                        componente[indice].push_back(vizitat[vizitat[0]]);
                        in_stiva[vizitat[vizitat[0]--]] = false;
                    }

                    componente[indice].push_back(nod_actual);
                }
            }
        }
    }
}

int main ()
{
    int numar_noduri , numar_muchii;
    cin >> numar_noduri >> numar_muchii;

    for (int nod[2] ; numar_muchii-- ; ) {
        cin >> nod[0] >> nod[1];
        adiacenta[nod[0]].push_back(nod[1]);
        adiacenta[nod[1]].push_back(nod[0]);
    }

    for (int indice = 1 ; indice <= numar_noduri ; indice++)
        { if (!moment[indice]) { Parcurgere(indice , 0); } }

    cout << componente.size() << '\n';

    for (auto componenta : componente) {
        for (auto nod_actual : componenta)
            { cout << nod_actual << ' '; }
        cout << '\n';
    }

    cout.close(); cin.close();
    return 0;
}