Cod sursa(job #2927526)

Utilizator AndreiBerbecaruBerbecaru-Iovan Andrei AndreiBerbecaru Data 20 octombrie 2022 19:30:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

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

vector<int> graf[100001], graf_transpus[100001], ctc[100001];
int vizitat[100001];
int n, m, x, y, nrctc, nod;
stack<int> s;

void citire(){
    fin>>n>>m;

    for(int i=1; i<=m; i++){
        fin>>x>>y;
        graf[x].push_back(y);
        graf_transpus[y].push_back(x);
    }
}

void DFS(int nod) {
    vizitat[nod] = 1;

    for (auto element : graf[nod]) {
        if (vizitat[element] == 0)
            DFS(element);
    }
    s.push(nod);
}

void DFS_transpus(int nod){
    vizitat[nod] = 0;
    ctc[nrctc].push_back(nod);

    for (auto element : graf_transpus[nod]) {
        if (vizitat[element] == true)
            DFS_transpus(element);
    }
}

void parcurgere(){
    for(int i=1; i<=n; i++){
        if(vizitat[i] == 0)
            DFS(i);
    }

    while(!s.empty()){
        nod = s.top();
        if(vizitat[nod] == 1){
            nrctc++;
            DFS_transpus(nod);
        }
        s.pop();
    }
}

void afisare(){
    fout<<nrctc<<"\n";
    for(int i = 1; i<=nrctc; i++){
        for(int j = 0; j < ctc[i].size(); j++)
            fout<<ctc[i][j]<<" ";
        fout<<"\n";
    }
}

int main(){
    citire();
    parcurgere();
    afisare();
}