Cod sursa(job #1921110)

Utilizator preda.andreiPreda Andrei preda.andrei Data 10 martie 2017 11:24:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

using Graph = vector<Node>;

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

    st.push(node);
    in_st[node] = true;

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

    if (g[node].lowpoint >= g[node].time) {
        vector<int> new_comp;
        do {
            new_comp.push_back(st.top());
            in_st[st.top()] = false;
            st.pop();
        } while (new_comp.back() != node);
        comps.push_back(new_comp);
    }
}

vector<vector<int>> FindComps(Graph &g)
{
    for (auto &node : g) {
        node.time = node.lowpoint = 0;
    }

    vector<vector<int>> comps;
    for (unsigned i = 0; i < g.size(); ++i) {
        if (g[i].time == 0) {
            stack<int> st;
            vector<bool> in_stack(g.size(), false);
            Dfs(g, st, in_stack, i, comps);
        }
    }
    return comps;
}

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

    int n, m;
    fin >> n >> m;

    Graph graph(n);
    while (m--) {
        int x, y;
        fin >> x >> y;
        graph[x - 1].edges.push_back(y - 1);
    }

    auto comp = FindComps(graph);
    fout << comp.size() << "\n";

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

    return 0;
}