Cod sursa(job #3168017)

Utilizator SSKMFSS KMF SSKMF Data 11 noiembrie 2023 13:21:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector <int> adiacenta[100001];
vector < vector <int> > componente;
int ordine[100001] , adancime[100001] , minim_accesibil[100001];
bool candidat[100001];

void Parcurgere (const int nod_actual)
{
    candidat[nod_actual] = true;
    ordine[++ordine[0]] = nod_actual;
    minim_accesibil[nod_actual] = adancime[nod_actual] = ++adancime[0];
    for (auto nod_vecin : adiacenta[nod_actual])
    {
        if (!adancime[nod_vecin])
            { adancime[nod_vecin] = adancime[nod_actual] + 1; Parcurgere(nod_vecin); minim_accesibil[nod_actual] = min(minim_accesibil[nod_actual] , minim_accesibil[nod_vecin]); }
        else if (candidat[nod_vecin])
            { minim_accesibil[nod_actual] = min(minim_accesibil[nod_actual] , adancime[nod_vecin]); }
    }

    if (adancime[nod_actual] == minim_accesibil[nod_actual])
    {
        int nod_componenta;
        componente.resize(componente.size() + 1);
        do { componente[componente.size() - 1].push_back(nod_componenta = ordine[ordine[0]--]); candidat[nod_componenta] = false; }
            while (nod_componenta != nod_actual);
    }
}

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

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

    for (int nod_actual = 1 ; nod_actual <= numar_noduri ; nod_actual++) {
        if (!adancime[nod_actual]) { Parcurgere(nod_actual); }
    }

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

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

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