Cod sursa(job #2666947)

Utilizator andrei.calin25Calin Andrei andrei.calin25 Data 2 noiembrie 2020 17:31:04
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;

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

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

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

void parcurgere(int i) {

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

    for(int j=0; j<muchie_din[i].size(); j++) {

        //cout<<muchie_din[i][j]<<' ';

        if (vizitat[muchie_din[i][j]] == 0) {
            parcurgere(muchie_din[i][j]);
            minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], minim_pe_ciclul_lui[muchie_din[i][j]]);
        }
        else if (e_in_stiva.find(muchie_din[i][j]) != e_in_stiva.end())
            minim_pe_ciclul_lui[i] = min(minim_pe_ciclul_lui[i], minim_pe_ciclul_lui[muchie_din[i][j]]);
    }

    if (minim_pe_ciclul_lui[i] == vizitat[i]) {

        //cout<<" terminat componenta"<<endl;
        int nod;

        do {
            nod = componenta_curenta.top();
            componenta_curenta.pop();
            e_in_stiva.erase(nod);
            componente[nr].push_back(nod);

        }   while (i!=nod);
    }

}

void afisare() {

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

int main() {

    citire();
    f.close();

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

    afisare();
    g.close();
}