Cod sursa(job #2572866)

Utilizator Iosif02Oprea Iosif Iosif02 Data 5 martie 2020 14:39:37
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAX = 200005;
int n, m, nr = 0;
bool vizitat[MAX];
vector <int> muchii[MAX], invers[MAX], componente[MAX];
stack <int> stiva;

void citire() {
    in >> n >> m;
    int x, y;
    for(int  i = 1; i <= m; i++) {
        in >> x >> y;
        muchii[x].push_back(y);
        invers[y].push_back(x);
    }
}

void DFS(int nodStart) {
    vizitat[nodStart] = true;
    for(unsigned int i = 0; i < muchii[nodStart].size(); i++) {
        int vecin = muchii[nodStart][i];
        if(!vizitat[vecin])
            DFS(vecin);
    }
    stiva.push(nodStart);
}

void DFS_T(int nodCurent) {
    vizitat[nodCurent] = false;
    componente[nr].push_back(nodCurent);
    for(unsigned int i = 0; i < invers[nodCurent].size(); i++) {
        int vecin = invers[nodCurent][i];
        if(vizitat[vecin])
            DFS_T(vecin);
    }
}

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

    while(!stiva.empty()) {
        int nodCurent = stiva.top();
        if(vizitat[nodCurent]) {
            nr++;
            DFS_T(nodCurent);
        }
        stiva.pop();
    }
}

void afisare() {
    out << nr << "\n";
    for(int i = 1; i <= nr; i++) {
        for(unsigned int j = 0; j < componente[i].size(); j++)
            out << componente[i][j] << " ";
        out << "\n";
    }
}

int main() {
    citire();
    Solve();
    afisare();
    return 0;
}