Cod sursa(job #3166750)

Utilizator SSKMFSS KMF SSKMF Data 9 noiembrie 2023 15:32:37
Problema Componente biconexe Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 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 nivel[100001] , minim_accesibil[1001] , parcurse[100001] , numar_componente;
bool vizitat[100001];

void Parcurgere (const int nod_actual , const int nod_sursa)
{
    vizitat[nod_actual] = true;
    parcurse[++parcurse[0]] = nod_actual;
    minim_accesibil[nod_actual] = nivel[nod_actual] = nivel[nod_sursa] + 1;
    for (auto nod_vecin : adiacenta[nod_actual]) {
        if (nod_vecin != nod_sursa)
        {
            if (!vizitat[nod_vecin])
            { 
                Parcurgere(nod_vecin , nod_actual); 

                if (nivel[nod_actual] <= minim_accesibil[nod_vecin])
                {
                    componente.resize(numar_componente + 1);
                    while (parcurse[parcurse[0]] != nod_actual)
                        { componente[numar_componente].push_back(parcurse[parcurse[0]--]); }

                    componente[numar_componente++].push_back(nod_actual);
                }
            }
            
            minim_accesibil[nod_actual] = min(minim_accesibil[nod_actual] , minim_accesibil[nod_vecin]);
        }
    }
}

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 nod_actual = 1 ; nod_actual <= numar_noduri ; nod_actual++) {
        if (!vizitat[nod_actual]) { Parcurgere(nod_actual , 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;
}