Cod sursa(job #2247416)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 septembrie 2018 16:24:23
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

struct Node
{
    int time = 0;
    int lowpoint = 0;
    vector<int> edges;
};

using Graph = vector<Node>;

vector<int> ExtractComp(stack<int> &st, int end_node)
{
    vector<int> comp;
    do {
        comp.push_back(st.top());
        st.pop();
    } while (!st.empty() && comp.back() != end_node);
    return comp;
}

void Dfs(Graph &g, int node, stack<int> &st, vector<vector<int>> &comps)
{
    static int time = 0;
    g[node].time = g[node].lowpoint = (time += 1);
    st.push(node);

    for (const auto &next : g[node].edges) {
        if (g[next].time == 0) {
            Dfs(g, next, st, comps);
            g[node].lowpoint = min(g[node].lowpoint, g[next].lowpoint);
        } else {
            g[node].lowpoint = min(g[node].lowpoint, g[next].time);
        }
    }

    if (g[node].lowpoint >= g[node].time) {
        auto new_comp = ExtractComp(st, node);
        comps.push_back(new_comp);
    }
}

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

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

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

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

    auto comps = GetComps(graph);
    fout << comps.size() << "\n";

    for (const auto &comp : comps) {
        for (const auto &node : comp) {
            fout << node + 1 << " ";
        }
        fout << "\n";
    }

    return 0;
}