Cod sursa(job #2726007)

Utilizator preda.andreiPreda Andrei preda.andrei Data 20 martie 2021 00:15:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

struct Node {
    vector<int> edges;
    int time = -1;
    int low = -1;
    bool in_stack = false;
};

using Graph = vector<Node>;
using Comp = vector<int>;

Comp ExtractComp(Graph& graph, stack<int>& st, int end_node) {
    Comp comp;
    while (comp.empty() || comp.back() != end_node) {
        comp.push_back(st.top());
        graph[st.top()].in_stack = false;
        st.pop();
    }
    return comp;
}

void Dfs(Graph& graph, int node, vector<Comp>& comps, stack<int>& st) {
    static auto time = 0;
    graph[node].time = graph[node].low = (time += 1);

    st.push(node);
    graph[node].in_stack = true;

    for (const auto& next : graph[node].edges) {
        if (graph[next].time == -1) {
            Dfs(graph, next, comps, st);
            graph[node].low = min(graph[node].low, graph[next].low);
        }
        if (graph[next].in_stack) {
            graph[node].low = min(graph[node].low, graph[next].time);
        }
    }

    if (graph[node].low >= graph[node].time) {
        comps.push_back(ExtractComp(graph, st, node));
    }
}

vector<Comp> FindComps(Graph& graph) {
    vector<Comp> comps;
    for (size_t i = 0; i < graph.size(); i += 1) {
        if (graph[i].time == -1) {
            stack<int> st;
            Dfs(graph, i, comps, st);
        }
    }
    return comps;
}

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

    int nodes, edges;
    fin >> nodes >> edges;

    Graph graph(nodes);
    for (auto i = 0; i < edges; i += 1) {
        int a, b;
        fin >> a >> b;
        graph[a - 1].edges.push_back(b - 1);
    }

    auto comps = FindComps(graph);
    fout << comps.size() << "\n";
    for (const auto& comp : comps) {
        for (const auto& node : comp) {
            fout << node + 1 << " ";
        }
        fout << "\n";
    }
    return 0;
}