Cod sursa(job #2904928)

Utilizator Mihai_BarbuMihai Barbu Mihai_Barbu Data 18 mai 2022 17:28:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <bits/stdc++.h>

std::vector<std::vector<int>> res;

std::stack<int> st;
std::vector<bool> curr_st;

void dfs(std::vector<std::vector<int>>& g, std::vector<int>& found,
         std::vector<int>& low_link, int& timestamp,
         int curr) {
    found[curr] = ++timestamp;
    low_link[curr] = found[curr];

    st.push(curr);
    curr_st[curr] = true;

    for (auto node : g[curr]) {
        if (found[node] != -1) {
            // visited
            // -- check if it is in
            //    the current stack
            if (curr_st[node]) {
                low_link[curr] = std::min(low_link[curr], found[node]);
            }

            continue;
        }

        // not visited
        dfs(g, found, low_link, timestamp, node);

        low_link[curr] = std::min(low_link[curr], low_link[node]);
    }

    if (low_link[curr] == found[curr]) {
        // no back edges from node
        std::vector<int> scc;

        do {
            int node = st.top();
            st.pop();

            curr_st[node] = false;

            scc.push_back(node);
        } while (scc.back() != curr);

        res.push_back(scc);
    }
}

void scc_tarjan(std::vector<std::vector<int>>& g, int V) {
    std::vector<int> found(V + 1, -1);
    std::vector<int> low_link(V + 1);

    curr_st = std::vector<bool>(V + 1);

    int timestamp;

    int node;
    for (node = 1; node <= V; ++node) {
        if (found[node] == -1) {
            timestamp = 0;

            dfs(g, found, low_link, timestamp, node);
        }
    }
}

int main() {
    FILE *fin = fopen("ctc.in", "r");
    std::ofstream fout("ctc.out");

    int V, E;

    fscanf(fin, "%d%d", &V, &E);
    std::vector<std::vector<int>> g(V + 1);

    int i, x, y;
    for (i = 0; i < E; ++i) {
        fscanf(fin, "%d%d", &x, &y);
        g[x].push_back(y);
    }

    scc_tarjan(g, V);

    int N = res.size();

    fout << N << "\n";

    for (i = 0; i < N; ++i) {
        for (auto node : res[i]) {
            fout << node << " ";
        }
        fout << "\n";
    }

    return 0;
}