Cod sursa(job #2886831)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 8 aprilie 2022 13:59:26
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <stack>
#include <vector>

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

int const NMAX = 1e5;
std::vector<int> G[NMAX + 5];

int currindex = 0;
int index[NMAX + 5];
int low[NMAX + 5];
bool onStack[NMAX + 5];

std::vector <std::vector <int>> scc;
int sccCount = 0;

std::stack<int> st;

void dfs(int node) {
    index[node] = ++currindex;
    low[node] = index[node];
    st.push(node);
    onStack[node] = true;

    for (auto x : G[node]) {
        if (index[x] == 0) {
            dfs(x);
            low[node] = std::min(low[node], low[x]);
        } else if (onStack[x])
            low[node] = std::min(low[node], index[x]);
    }

    if (low[node] == index[node]) {
        sccCount++, scc.push_back({});
        while (!st.empty()) {
            int x = st.top(); st.pop();
            scc[sccCount - 1].push_back(x);
            onStack[x] = false;
            if (x == node)
                break;
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }
    dfs (1);
    fout << sccCount << "\n";
    for (int i = 0; i < sccCount; i++) {
        int size = scc[i].size();
        for (int j = 0; j < size; j++)
            fout << scc[i][j] << " ";
        fout << "\n";
    }
    return 0;
}