Cod sursa(job #951090)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 19 mai 2013 11:43:07
Problema Componente tare conexe Scor 54
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <string>
#include <stack>

using namespace std;

fstream in, out;
vector<int> *graf, *grafT, *compCTC;
stack<int> stiva;
bitset<100001> vizitat;
int nrNoduri, nrMuchii, nrCTC;

void dfsGT(int);
void dfs(int);
void start();


int main()
{
    in.open("ctc.in", ios::in);
    out.open("ctc.out", ios::out);

    int aux1, aux2;
    in >> nrNoduri >> nrMuchii;
    graf = new vector<int> [nrNoduri + 1];
    grafT = new vector<int> [nrNoduri + 1];
    compCTC = new vector<int> [nrNoduri + 1];

    for (int i = 1; i <= nrMuchii; i++){

        in >> aux1 >> aux2;
        graf[aux1].push_back(aux2);
        grafT[aux2].push_back(aux1);
    }

    start();

    out << nrCTC << endl;
    for (int i = 1; i <= nrCTC; i++){

        for (int j = 0; j < compCTC[i].size(); j++){

            out << compCTC[i][j] << " ";
        }
        out << endl;
    }




    return 0;
}

void start(){


    //fill (vizitat, vizitat + 100001, 0);
    vizitat.reset();
    for (int i = 1; i <= nrNoduri; ++i){

        if (!vizitat[i]){

            dfs(i);
            stiva.push(i);
        }
    }

    //fill (vizitat, vizitat + 100001, 0);
    vizitat.reset();
    while (!stiva.empty()){

        int x = stiva.top();
        nrCTC++;
        dfsGT(x);
        int aux = stiva.top();
        compCTC[nrCTC].push_back(aux);
        stiva.pop();
    }

}
void dfsGT(int x){

    vizitat[x] = 1;
    for (int i = 0; i < grafT[x].size(); i++){

        int y = grafT[x][i];
        if (!vizitat[y]){

            dfsGT(y);
            int aux = stiva.top();
            compCTC[nrCTC].push_back(aux);
            stiva.pop();
        }
    }

}
void dfs(int x){

    vizitat[x] = 1;
    for (int i = 0; i < graf[x].size(); i++){
        int y;
        y = graf[x][i];
        if (!vizitat[y]){

            dfs(y);
            stiva.push(y);

        }
    }

}