Cod sursa(job #3204048)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 15 februarie 2024 15:37:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int Nmax = 100005;

struct nod{
    vector<int> vecini;
    int timp_introdus, low;
    bool inStiva;
};

int n, m, timp;
nod nodes[Nmax];
stack<int> st;
vector<int> ctc;
vector<vector<int>> componente;

void citire(){
    ifstream fin("ctc.in");

    int start, finish;

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> start >> finish;
        nodes[start].vecini.push_back(finish);
    }
}

void elimina_din_stiva(){
    nodes[st.top()].inStiva = 0;
    ctc.push_back(st.top());
    st.pop();
}

void marcare_componenta(int root){
    ctc.clear();

    while(st.top() != root){
        elimina_din_stiva();
    }
    elimina_din_stiva();

    componente.push_back(ctc);
}

void dfs(int nod){
    nodes[nod].timp_introdus = nodes[nod].low = ++timp;
    nodes[nod].inStiva = 1;
    st.push(nod);

    for(int vecin : nodes[nod].vecini){
        if(!nodes[vecin].timp_introdus){
            dfs(vecin);
            nodes[nod].low = min(nodes[nod].low, nodes[vecin].low);
        }
        else if(nodes[vecin].inStiva){
            nodes[nod].low = min(nodes[nod].low, nodes[vecin].low);
        }
    }

    if(nodes[nod].timp_introdus == nodes[nod].low){
        marcare_componenta(nod);
    }
}

void dfs_starter(){
    timp = 0;
    for(int i = 1; i <= n; i++){
        if(!nodes[i].timp_introdus){
            dfs(i);
        }
    }
}

void afisare_componente(){
    fout << componente.size() << '\n';

    for(vector<int> ctc : componente){
        for(int element : ctc){
            fout << element << " ";
        }
        fout << '\n';
    }
}

int main(){
    citire();

    dfs_starter();

    afisare_componente();

    return 0;
}