Cod sursa(job #2338547)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 7 februarie 2019 16:39:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include    <iostream>
#include    <fstream>
#include    <vector>
#include    <stack>

using namespace std;

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

#define NMax 100005
vector < int > G[NMax], GT[NMax], result[NMax];
stack < int > S;

int N, M, NrCTC;
int beenThere[NMax];

void Read(){
    fin >> N >> M;
    for(int i = 1; i <= M; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void DFS(int Nod){
    beenThere[Nod] = 1;
    // Zona 1
    for(unsigned int i = 0; i < G[Nod].size(); i++){
        // Zona 2
        int Vecin = G[Nod][i];
        if(!beenThere[Vecin])
            DFS(Vecin);
        //Zona 3
    }
    S.push(Nod);
    //Zona 4
}

void DFS_T(int Nod){
    beenThere[Nod] = 2;
    result[NrCTC].push_back(Nod);

    for(unsigned int i = 0; i < GT[Nod].size(); i++){
        int Vecin = GT[Nod][i];
        if(beenThere[Vecin] == 1)
            DFS_T(Vecin);
    }
}

void Solve(){
    for(int i = 1; i <= N; i++)
        if(!beenThere[i])
            DFS(i);

    while(!S.empty()){
        int Nod = S.top();
        //cout << Nod << " ";
        if(beenThere[Nod] == 1){
            NrCTC++;
            DFS_T(Nod);
        }
        S.pop();
    }
}

void Print(){
    fout << NrCTC << "\n";
    for(int i = 1; i <= NrCTC; i++){
        for(unsigned int j = 0; j < result[i].size(); j++)
            fout << result[i][j] << " ";
        fout << "\n";
    }
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}