Cod sursa(job #2668045)

Utilizator andrei.calin25Calin Andrei andrei.calin25 Data 4 noiembrie 2020 13:23:58
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int vizitat[100001], minim_pe_ciclul_lui[100001];
bool e_in_stiva[100001];
vector<int> muchie_din[100001], auxiliar;
vector<vector<int>> componente;
stack<int> componenta_curenta;
int n, m, curent = 1;

void citire() {
    f>>n>>m;
    for(int i=0; i<m; i++) {
        int a, b;
        f>>a>>b;
        muchie_din[a].push_back(b);
    }

    f.close();
}

void parcurgere(int i) {

    vizitat[i] = minim_pe_ciclul_lui[i] = curent++;
    componenta_curenta.push(i);
    e_in_stiva[i] = 1;

    for(int j : muchie_din[i]) {

        if (vizitat[j] == 0) {
            parcurgere(j);
            minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], minim_pe_ciclul_lui[j]);
        }
        else if (e_in_stiva[j] == 1)
            minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], vizitat[j]);
    }

    if (minim_pe_ciclul_lui[i] == vizitat[i]) {
        int nod;
        auxiliar.clear();

        do {
            nod = componenta_curenta.top();
            componenta_curenta.pop();
            e_in_stiva[nod] = 0;
            auxiliar.push_back(nod);

        }   while (nod!=i);


        componente.push_back(auxiliar);
    }
}

void afisare() {

    g<<componente.size()<<endl;

    for(int i=0; i<componente.size(); i++) {
        for(int j : componente[i])
            g<<j<<' ';
        g<<endl;
    }

    g.close();

}

int main() {

    citire();

    for(int i=1; i<=n; i++)
        if (vizitat[i] == 0)
            parcurgere(i);

    afisare();

}