Cod sursa(job #2927769)

Utilizator soda-popClinciu Diana soda-pop Data 21 octombrie 2022 15:02:31
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

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

void CreareGrafSiGrafTranspus(int m, vector<int> listaAdiacentaG[], vector<int> listaAdiacentaGt[]) {
    int x, y;
    for (int i = 0; i <= m - 1; i++) {
        in >> x >> y;
        listaAdiacentaG[x].push_back(y);
        listaAdiacentaGt[y].push_back(x);
    }
}

void DFS_G(int start, int viz[], vector<int> listaAdiacentaG[], stack<int> &stiva) {
    viz[start] = 1;
    for (auto it = listaAdiacentaG[start].begin(); it!=listaAdiacentaG[start].end(); it++) {
        int y = *it;
        if (viz[y] == 0)
            DFS_G(y, viz, listaAdiacentaG, stiva);
    }
    stiva.push(start);
}

void DFS_Gt(int start, int viz[], vector<int> listaAdiacentaGt[], vector<int> &parcurgere) {
    viz[start] = 1;
    parcurgere.push_back(start);
    for (auto it = listaAdiacentaGt[start].begin(); it!=listaAdiacentaGt[start].end(); it++) {
        int y = *it;
        if (viz[y] == 0)
            DFS_Gt(y, viz, listaAdiacentaGt, parcurgere);
    }
}

int main() {
    int m, n;
    vector<int> listaAdiacentaG[25001], listaAdiacentaGt[25001];

    in >> n >> m;
    CreareGrafSiGrafTranspus(m, listaAdiacentaG, listaAdiacentaGt);

    stack<int> stiva;
    int viz[25001] = {0};
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
            DFS_G(i, viz, listaAdiacentaG, stiva);

    for (int i = 1; i <= n; i++)
        viz[i] = 0;

    int nrCompConexe = 0;
    vector<vector<int>> compConexe;
    while (!stiva.empty()) {
        int x = stiva.top();
        stiva.pop();
        if (viz[x] == 0) {
            nrCompConexe++;

            vector<int> parcurgere;
            DFS_Gt(x, viz, listaAdiacentaGt, parcurgere);

            compConexe.push_back(parcurgere);
        }
    }

    out << nrCompConexe << endl;
    for (int i = 0; i < nrCompConexe; i++) {
        for(auto it = compConexe[i].begin(); it !=compConexe[i].end(); it++)
            out << *it << ' ';
        out << endl;
    }

    return 0;
}