Cod sursa(job #2925849)

Utilizator iulia.talpalariuIulia-Georgiana Talpalariu iulia.talpalariu Data 16 octombrie 2022 11:33:29
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
//#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream fileIn("ctc.in");
ofstream fileOut("ctc.out");


class Graph {
    int N;
    int M;
    vector<vector<int>> list_ad;
    vector<vector<int>> ctc;
    int count_ctc;


    public:
        void read();
        void ctc_tarjan();
        void strong_connected(int node, vector<int>& index, vector<int>& lowlink,
                              vector<bool>& onstack, stack<int>& stk, int i);

};

void Graph:: read() {
    fileIn >> N >> M;
    // resize
    list_ad.resize(N + 1);

    int a, b;
    for(int i=0; i<= M-1; i++) {
            fileIn >> a >> b;
            list_ad[a].push_back(b);
    }

}

void Graph::strong_connected(int node, vector<int>& index, vector<int>& lowlink,
vector<bool>& onstack, stack<int>& stk, int i) {
    index[node] = lowlink[node] = i++;
    stk.push(node);
    onstack[node] = true;

    for( int neib: list_ad[node]) {
        if (index[neib] == -1) {
            strong_connected(neib, index, lowlink, onstack, stk, i);
            // callback
        }
        if (onstack[neib]) {
            lowlink[node] = min(lowlink[node], lowlink[neib]);

        }
    }

    if (lowlink[node] == index[node]) {
        //finished visiting all nodes in the current scc
        int k;
        count_ctc ++;
        ctc.push_back({});
        do {
            k = stk.top();
            stk.pop();
            onstack[k] = false;
            lowlink[k] = index[node];
            ctc[count_ctc].push_back(k);
        } while(k != node);
    }

}



void Graph::ctc_tarjan() {
    count_ctc = 0;
    ctc.push_back({});
    vector<int> index(N + 1, -1);
    vector<int> lowlink(N + 1, -1);
    vector<bool> onstack(N + 1, false);
    stack<int> stk;

    for(int node = 1; node <= N; node++) {
        if (index[node] == -1) {
            strong_connected(node, index, lowlink, onstack, stk, 0);
        }
    }
    fileOut << count_ctc;
    for(auto scc: ctc) {
        for( auto comp: scc) {
            fileOut << comp << " ";
        }
        fileOut<< "\n";
    }

}




int main()  {
    Graph my_graph;
    my_graph.read();
    my_graph.ctc_tarjan();


    return 0;



}