Cod sursa(job #2464900)

Utilizator andreioneaAndrei Onea andreionea Data 29 septembrie 2019 08:06:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.94 kb
#include <unordered_map>
#include <vector>
#include <fstream>
#include <stack>
#include <algorithm>

using std::vector;
using std::unordered_map;
using std::stack;
struct Vertex {
    using IndexType = int;
    IndexType id;
    vector<IndexType> outEdges;
    static constexpr IndexType UndefinedIndex = -1;
    IndexType index = UndefinedIndex;
    IndexType lowLink = UndefinedIndex;
    bool onStack = false;
};

struct Graph {
    using VertexIdx = Vertex::IndexType;
    unordered_map<VertexIdx, Vertex> vertices;
    template<typename T>
    static Graph fromStrean(T& stream) {
        int n, m;
        stream >> n >> m;
        Graph ret;
        for (int i = 0; i < m; ++i) {
            VertexIdx a, b;
            stream >> a >> b;
            ret.vertices[a].id = a;
            ret.vertices[b].id = b;
            ret.vertices[a].outEdges.push_back(b);
        }
        return ret;
    }
    using StrongConnectComponent = vector<VertexIdx>;
    using TarjanSol = vector<StrongConnectComponent>;
    TarjanSol tarjan() {
        TarjanSol sol;
        VertexIdx index = 0;
        stack<VertexIdx> s;
        for(auto& it : vertices) {
            Vertex& v = it.second;
            if (v.index == Vertex::UndefinedIndex) {
                strongConnect(sol, v, index, s);
            }
        }
        return sol;
    }
    void strongConnect(TarjanSol& sol, Vertex& v, VertexIdx& index, stack<VertexIdx>& s) {
        v.index = index;
        v.lowLink = index;
        ++index;
        s.push(v.id);
        v.onStack = true;
        for (VertexIdx idx : v.outEdges) {
            Vertex& w = vertices[idx];
            if (w.index == Vertex::UndefinedIndex) {
                strongConnect(sol, w, index, s);
                if (v.lowLink != Vertex::UndefinedIndex) {
                    v.lowLink = std::min(v.lowLink, w.lowLink);
                } else {
                    v.lowLink = w.lowLink;
                }
            } else if (w.onStack) {
                if (v.lowLink != Vertex::UndefinedIndex) {
                    v.lowLink = std::min(v.lowLink, w.index);
                } else {
                    v.lowLink = w.index;
                }
                
            }
        }
        if (v.lowLink == v.index) {
            StrongConnectComponent scc;
            while(s.top() != v.id) {
                Vertex& w = vertices[s.top()];
                s.pop();
                w.onStack = false;
                scc.push_back(w.id);
            }
            s.pop();
            v.onStack = false;
            scc.push_back(v.id);
            sol.emplace_back(std::move(scc));
        }
    }
};

int main()
{
    std::ifstream fin("ctc.in");
    std::ofstream fout("ctc.out");
    Graph g = Graph::fromStrean(fin);
    const auto solutions = g.tarjan();
    fout << solutions.size() << "\n";
    for (const auto& solution: solutions) {
        for (const auto id: solution) {
            fout << id << " ";
        }
        fout << "\n";
    }
    return 0;
}