Cod sursa(job #1831855)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 18 decembrie 2016 21:33:17
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.53 kb
#include <bits/stdc++.h>
using namespace std;

class Graph {

    private:
    int nodes;
    vector <vector<int>> graph;
    vector <vector<int>> SCC;

    vector <int> idx, lowlink;
    stack <int> stiva;
    vector<bool> inStack;
    int index;

    int nrSCC;


    void Tarjan(int node) {

        if (idx[node] != 0)
            return;

        vector <int> :: iterator it;

        idx[node] = lowlink[node] = index++;
        stiva.push(node);
        inStack[node] = 1;

        for (auto it : graph[node]) {
            if (!idx[it]) {
                Tarjan(it);
                lowlink[node] = min(lowlink[node], lowlink[it]);
            }
            else {
                if (inStack[it])
                    lowlink[node] = min(lowlink[node], idx[it]);
            }
        }

        if (lowlink[node] == idx[node]) {
            int k;

            nrSCC++;

            do {
                k = stiva.top();
                stiva.pop();
                inStack[k] = 0;
                SCC[nrSCC].push_back(k);
            }while (k != node);
        }
    }

    public:

        Graph(int nodes) {
            this->nodes = nodes;
            this->inStack.resize(nodes + 1);
            this->graph.resize(nodes + 1);
            this->idx.resize(nodes + 1);
            this->lowlink.resize(nodes + 1);
            this->index = 0;
            this->nrSCC = 0;
        }

        void addEdge(const int x, const int y) {
            this->graph[x].push_back(y);
        }


        vector<vector<int>> getSCC() {

            SCC.resize(nodes + 1);

            for (int i = 1; i <= nodes; ++i)
                if (!idx[i])
                    Tarjan(i);

            for (int i = 0; !nrSCC && i < nrSCC; ++i)
                for (auto it : SCC[i])
                    SCC[i].push_back(it);

            return SCC;
        }

        int countSCC() {

            if (!nrSCC)
                getSCC();

            return this->nrSCC;
        }
};

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

int main() {

    int N, M;

    fin >> N >> M;

    Graph myGraph(N);

    while (M--) {
        int x, y;
        fin >> x >> y;
        myGraph.addEdge(x, y);
    }

    vector<vector<int>> CTC(N + 1);
    CTC = myGraph.getSCC();

    fout << myGraph.countSCC() << "\n";

    for (int i = 1; i <= myGraph.countSCC(); ++i) {
        for (auto it : CTC[i])
            fout << it << " ";

        fout << "\n";
    }

    return 0;
}