Cod sursa(job #1194371)

Utilizator Catah15Catalin Haidau Catah15 Data 3 iunie 2014 17:49:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define maxN 100005
#define PB push_back

vector <int> dGraph[maxN], tGraph[maxN], sol[maxN], Q;
bool viz[maxN];
int N, M, nrCTC;


void DFP(int nod) {
    viz[nod] = true;

    for(unsigned int i = 0; i < dGraph[nod].size(); ++ i) {
        int nod2 = dGraph[nod][i];

        if(viz[nod2]) continue;
        DFP(nod2);
    }

    Q.PB(nod);
}

void DFM(int nod) {
    viz[nod] = true;
    sol[nrCTC].PB(nod);

    for(unsigned int i = 0; i < tGraph[nod].size(); ++ i) {
        int nod2 = tGraph[nod][i];

        if(viz[nod2]) continue;
        DFM(nod2);
    }
}

void kosaraju() {
    for(int i = 1; i <= N; ++ i) {
        if(viz[i]) continue;
        DFP(i);
    }

    for(int i = 1; i <= N; ++ i)
        viz[i] = false;

    for(int i = Q.size() - 1; i >= 0; -- i) {
        int nod = Q[i];
        if(viz[nod]) continue;

        ++ nrCTC;
        DFM(nod);
    }
}

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

    f >> N >> M;

    while(M --) {
        int x, y;
        f >> x >> y;

        dGraph[x].PB(y);
        tGraph[y].PB(x);
    }

    kosaraju();

    g << nrCTC << '\n';
    for(int i = 1; i <= nrCTC; ++ i) {
        for(unsigned int j = 0; j < sol[i].size(); ++ j)
            g << sol[i][j] << " ";
        g << '\n';
    }

    return 0;
}