Cod sursa(job #3188120)

Utilizator SSKMFSS KMF SSKMF Data 1 ianuarie 2024 19:13:07
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 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];

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

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

                while (vizitat[vizitat[0]] != nod_actual) {
                    componente[indice].push_back(vizitat[vizitat[0]--]);
                }

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

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

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

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