Cod sursa(job #2922182)

Utilizator livliviLivia Magureanu livlivi Data 5 septembrie 2022 17:17:30
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

class Graph {
private:
    int size_;
    vector<vector<int>> edges_;
    vector<vector<int>> ctc_;

    vector<int> low_;
    vector<int> d_;
    vector<bool> on_stk_;
    stack<int> stk_;

public:
    Graph(int size) {
        size_ = size;
        edges_.resize(size_);
    }

    void addEdge(int a, int b) {
        edges_[a].push_back(b);
    }

    int dfs(int node, int& index) {
        d_[node] = index;
        index++;
        low_[node] = d_[node];

        stk_.push(node);
        on_stk_[node] = true;

//        string space(d_[node], ' ');
//        cerr << space << node + 1 << endl;

        for (int i = 0; i < edges_[node].size(); i++) {
            int next = edges_[node][i];
            if (d_[next] == 0) {
                low_[node] = min(low_[node], dfs(next, index));
            } else if (on_stk_[next]) {
                low_[node] = min(low_[node], d_[next]);
            }
        }

//        cerr << space << node + 1 << " " << d_[node] << " " << low_[node] << endl;

        if (low_[node] == d_[node]) {
            ctc_.push_back(vector<int>());
            while (stk_.top() != node) {
                ctc_.back().push_back(stk_.top());
                stk_.pop();
            }
            ctc_.back().push_back(stk_.top());  // node
            stk_.pop();
        }

        return low_[node];
    }

    void computeCtc() {
        low_.clear();
        d_.clear();
        on_stk_.clear();
        ctc_.clear();

        low_.resize(size_);
        d_.resize(size_, 0);
        on_stk_.resize(size_, false);

        int index = 1;
        for (int i = 0; i < size_; i++) {
            if (d_[i] == 0) {
                dfs(i, index);
            }
        }
    }

    void printCtc(ostream& out) {
        out << ctc_.size() << "\n";
        for (int i = 0; i < ctc_.size(); i++) {
            for (int j = 0; j < ctc_[i].size(); j++) {
                out << ctc_[i][j] + 1 << " ";
            }
            out << "\n";
        }
    }
};

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

    int n, m; in >> n >> m;
    Graph graph(n);

    for(int i = 0; i < m; i++) {
        int a, b; in >> a >> b;
        a--; b--;
        graph.addEdge(a, b);
    }

    graph.computeCtc();
    graph.printCtc(out);

    return 0;
}