Cod sursa(job #2908044)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 1 iunie 2022 11:05:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>


using namespace std;

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

int n, m; // numarul de noduri, respectiv de muchii
vector<vector<int>>vecini; // liste de vecini
vector<bool>vizitat; // marcarea varfurilor vizitate in parcurgere
vector<vector<int>>veciniTranspus; // liste de vecini pentru graful transpus
stack<int>timpiFinalizare; // stiva in care stochez nodurile in ordinea desc a timpilor de finalizare
vector<vector<int>>componenteTareConexe; // stochez pentru fiecare componenta tare conexa nodurile care o alcatuiesc
int nrComponenteTareConexe;

void dfs(int u){

    vizitat[u] = 1;

    for(int i = 0; i < vecini[u].size(); i++)
        if(!vizitat[vecini[u][i]])
            dfs(vecini[u][i]);

timpiFinalizare.push(u);
}

void dfsTranspus(int u){

     componenteTareConexe[nrComponenteTareConexe].push_back(u);
     vizitat[u] = 1;

     for(int i = 0; i < veciniTranspus[u].size(); i++)
        if(!vizitat[veciniTranspus[u][i]])
            dfsTranspus(veciniTranspus[u][i]);
}


int main()
{
    f >> n >> m;

    vecini.resize(n + 1);
    vizitat.resize(n + 1, 0);
    veciniTranspus.resize(n + 1);
    componenteTareConexe.resize(n + 1);

    for(int i = 0; i < m; i++){

        int u, v;

        f >> u >> v;

        vecini[u].push_back(v);
        veciniTranspus[v].push_back(u);
    }

    // prima parcurgere o facem in graful normal
    // pentru a determina timpii de finalizare
    for(int i = 1; i <= n; i++)
        if(!vizitat[i])
            dfs(i);

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

    // a doua parcurgere o sa fie facuta in graful transpus
    // si de asemenea o sa tinem cont de timpii de finalizare determinati mai sus
    while(!timpiFinalizare.empty()){

        int u = timpiFinalizare.top();
        timpiFinalizare.pop();

        if(!vizitat[u]){
            nrComponenteTareConexe++;
            dfsTranspus(u);
        }
    }

    g << nrComponenteTareConexe << "\n";

    for(int i = 1; i <= nrComponenteTareConexe; i++){
        for(int j = 0; j < componenteTareConexe[i].size(); j++)
            g << componenteTareConexe[i][j] << " ";
        g << "\n";

    }

    return 0;
}