Cod sursa(job #2306062)

Utilizator flatmapLambda flatmap Data 21 decembrie 2018 16:22:37
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define INPUT_FILE_PATH "ctc.in"
#define OUTPUT_FILE_PATH "ctc.out"
#define UNDEFINED -1

using namespace std;

class Graph {
public:
    Graph(int n) : n(n) {
        index = new int[n];
        lowLink = new int[n];
        isInStack = new bool[n];
        fill(index, index + n, UNDEFINED);
        fill(lowLink, lowLink + n, UNDEFINED);
        fill(isInStack, isInStack + n, false);
        for (int i = 0; i < n; ++i) {
            adjMatrix.emplace_back(vector<int>());
        }
    }

    void addEdge(int from, int to) {
        adjMatrix[from].emplace_back(to);
    }

    vector<vector<int>> getStrongConnectedComponents() {
        currIndex = 0;
        for (int i = 0; i < n; ++i) {
            if (index[i] == UNDEFINED) {
                tarjan(i);
            }
        }
        return strongConnectedComponents;
    }

private:
    int n;
    int *index;
    int *lowLink;
    bool *isInStack;
    int currIndex;
    vector<vector<int>> adjMatrix;
    vector<vector<int>> strongConnectedComponents;
    stack<int> st;

    void tarjan(int node) {
        index[node] = currIndex++;
        lowLink[node] = index[node];
        st.push(node);
        isInStack[node] = true;
        for (int target : adjMatrix[node]) {
            if (index[target] == UNDEFINED) {
                tarjan(target);
                lowLink[node] = min(lowLink[node], lowLink[target]);
            } else if (isInStack[target]) {
                lowLink[node] = min(lowLink[node], lowLink[target]);
            }
        }
        if (index[node] == lowLink[node]) {
            strongConnectedComponents.emplace_back(vector<int>());
            int top;
            do {
                top = st.top();
                isInStack[node] = false;
                st.pop();
                strongConnectedComponents[strongConnectedComponents.size() - 1].push_back(top);
            } while (top != node);
        }
    }
};

int main() {
    ifstream cin(INPUT_FILE_PATH);
    ofstream cout(OUTPUT_FILE_PATH);
    int n, m;
    cin >> n >> m;
    Graph graph(n);
    while (m--) {
        int from, to;
        cin >> from >> to;
        --from;
        --to;
        graph.addEdge(from, to);
    }
    vector<vector<int>> strongConnComponents = graph.getStrongConnectedComponents();
    cout << strongConnComponents.size() << "\n";
    for (const vector<int> &nodes : strongConnComponents) {
        for (int node : nodes) {
            cout << node + 1 << " ";
        }
        cout << "\n";
    }
    return 0;
}