Cod sursa(job #2927851)

Utilizator anne_marieMessner Anne anne_marie Data 21 octombrie 2022 18:05:30
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, u, v, ind_var;
int nr_componente;

vector<bool> onStack(100005); // daca nodul mai e pe stack
vector<int> ind(100005); // ordinea de vizitare a nodurilor
vector<int> lowlink(100005); // indexul cel mai mic al unui nod din componenta tare conexa
vector<vector<int>> ad(100005); // lista de adiacente
vector<vector<int>> result(100005);
stack<int> st;

void dfs(int node){
    ind_var ++;
    ind[node] = ind_var;
    lowlink[node] = ind_var;
    st.push(node);
    onStack[node] = true;


    // parcurg vecinii & update lowlink
    for(auto vec : ad[node]) {
        if (ind[vec] == 0) {
            dfs(vec);
            lowlink[node] = min(lowlink[node], lowlink[vec]);
        } else if (onStack[vec])
            lowlink[node] = min(lowlink[node], lowlink[vec]);
    }

    if(ind[node] == lowlink[node]) {
        // este inceputul unei componente tare conexe
        // in stiva vor fi restul componentelor componentei conexe
        nr_componente ++;
        u = st.top();

        while(node != u) // adaugam componenta la result
        {
            result[nr_componente].push_back(u);
            onStack[u] = false;
            st.pop();
            u = st.top();
        }
        result[nr_componente].push_back(u);
        st.pop();
        onStack[u] = false;
    }


}

int main()
{
    fin >> n >> m;

    // lista de adiacente
    for(int i = 1; i <= m; i ++){
        fin >> u >> v;
        ad[u].push_back(v);
    }

    ind_var  = 0;
    for(int i = 1; i <= n; i ++){
        if(ind[i] == 0){
            dfs(i);
        }
    }


    fout << nr_componente << '\n';
    for(int i = 1; i <= nr_componente; i ++) {
        for(auto node : result[i])
            fout << node << " ";
        fout << '\n';
    }
}