Cod sursa(job #2928443)

Utilizator alexdn6Dina Alexandru alexdn6 Data 22 octombrie 2022 22:05:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
stack <int> stiva;
vector <bool> peStiva;
vector <int> lowlink, index;
int timp = 0, nrCtc = 0;
vector <vector<int>> lista_ad, componente;
void tareConexe(int nod) {

    index[nod] = timp;
    lowlink[nod] = timp;
    timp += 1;
    stiva.push(nod);
    peStiva[nod] = true;

    for(auto n: lista_ad[nod]) {
        if (index[n] == -1) {
            tareConexe(n);
            lowlink[nod] = min(lowlink[nod], lowlink[n]);
        }
        else if(peStiva[n])
            lowlink[nod] = min(lowlink[nod], index[n]);
    }
    if(lowlink[nod] == index[nod]) {

        while(stiva.top() != nod) {
            peStiva[stiva.top()] = false;
            componente[nrCtc].push_back(stiva.top());
            stiva.pop();
        }
        componente[nrCtc].push_back(stiva.top());
        nrCtc++;
        peStiva[stiva.top()] = false;
        stiva.pop();
    }
}
int main() {
    int n, m;
    f >> n >> m;
    lista_ad.resize(n + 1);
    index.resize(n + 1, -1);
    lowlink.resize(n + 1, -1);
    peStiva.resize(n + 1, false);
    componente.resize(m);
    for(int i = 1; i <= m; i++) {
        int a, b;
        f >> a >> b;
        lista_ad[a].push_back(b);
    }
//    for(int i = 1; i <= n; i++) {
//        cout << i << " : ";
//        for(int j = 0; j < lista_ad[i].size(); j++)
//            cout << lista_ad[i][j] << " ";
//        cout << endl;
//    }
    for(int i = 1; i <= n; i++)
        if(index[i] == -1) {
            tareConexe(i);
        }
    g << nrCtc << "\n";
    for(int i = 0; i < nrCtc; i++) {
        for(int j = 0; j < componente[i].size(); j++)
            g << componente[i][j] << " ";
        g << "\n";
    }
    return 0;
}