Cod sursa(job #2925282)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 13 octombrie 2022 16:04:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1e5;

int id, lowViz[NMAX + 5];

void getComp(int nod, vector<vector<int>> &compList, bool onStack[], stack<int> &stackNodes) {
    vector<int> comp;

    while(stackNodes.top() != nod) {
        comp.emplace_back(stackNodes.top());
        onStack[stackNodes.top()] = 0;
        stackNodes.pop();
    }

    comp.emplace_back(nod);
    onStack[nod] = 0;
    stackNodes.pop();
    compList.push_back(comp);
}

void dfs(int nod, vector<int> G[], int viz[], bool onStack[], vector<vector<int>> &compList, stack<int> &stackNodes) {
    viz[nod] = lowViz[nod] = ++id;
    onStack[nod] = 1;
    stackNodes.push(nod);

    for(auto &vec : G[nod]) {
        if(onStack[vec]) {
            lowViz[nod] = min(lowViz[nod], viz[vec]);
        } else if(!viz[vec]) {
            dfs(vec, G, viz, onStack, compList, stackNodes);
            lowViz[nod] = min(lowViz[nod], lowViz[vec]);
        }
    }

    if(viz[nod] == lowViz[nod])
        getComp(nod, compList, onStack, stackNodes);
}

int main()
{
    ios::sync_with_stdio(false);
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int n, m;

    fin >> n >> m;

    vector<int> G[n + 1];

    for(int i = 1; i <= m; i++) {
        int a, b;

        fin >> a >> b;

        G[a].emplace_back(b);
    }

    int viz[n + 1];
    bool onStack[n + 1];

    for(int i = 1; i <= n; i++)
        viz[i] = onStack[i] = 0;

    vector<vector<int>> compList;
    stack<int> stackNodes;

    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i, G, viz, onStack, compList, stackNodes);

    fout << compList.size() << '\n';

    for(auto &comp : compList) {
        for(auto &nod : comp)
            fout << nod << " ";

        fout << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}