Cod sursa(job #2572860)

Utilizator Iosif02Oprea Iosif Iosif02 Data 5 martie 2020 14:37:54
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 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> 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;
        invers[y].push_back(x);
    }
}

void DFS_T(int nodCurent) {
    vizitat[nodCurent] = true;
    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++) {
        int nodCurent = i;
        if(!vizitat[nodCurent]) {
            nr++;
            DFS_T(nodCurent);
        }
    }
}

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;
}