Cod sursa(job #2929513)

Utilizator GeorgeNistorNistor Gheorghe GeorgeNistor Data 25 octombrie 2022 23:35:45
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>

using namespace std;

vector<vector<int>> graf;
vector<vector<int>> grafTranspus;
vector<bool> vizitat;
stack<int> stiva;
vector<vector<int>> lista_ctc;
int N, M;

void citireGraf(){
    ifstream fin("ctc.in");
    fin >> N >> M;
    graf = vector<vector<int>>(N+1);
    vizitat = vector<bool>(N+1);
    for(int i = 0; i < M; i++){
        int nod_1, nod_2;
        fin >> nod_1 >> nod_2;
        graf[nod_1].push_back(nod_2);
    }
}

void DFS(vector<vector<int>> g, int nod_start, vector<int> &ctc, bool transpus = false){
    if(transpus)
        ctc.push_back(nod_start);
    vizitat[nod_start] = true;
    for(auto nod_vecin: g[nod_start])
        if(!vizitat[nod_vecin])
            DFS(g, nod_vecin, ctc, transpus);
    if(!transpus)
        stiva.push(nod_start);
}
int main() {
    citireGraf();
    // Pasul 0 - Construim grafTranspus
    grafTranspus = vector<vector<int>>(N+1);
    for(int i = 1; i <= N; i++)
        for(auto nod_vecin: graf[i])
            grafTranspus[nod_vecin].push_back(i);
    // Pasul 1 - Parcurgem DFS graf si introducem intr-o stiva fiecare varf la momentul in care este finalizat
    vector<int> temp;
    for(int i = 1; i <= N; i++)
        if(!vizitat[i])
            DFS(graf, i, temp, false);
    // Pasul 2 - Parcurgem DFS grafTranspus considerand varfurile in ordinea in care sunt extrase din S
    vizitat = vector<bool> (N+1);
    while(!stiva.empty()){
        int nod_curent = stiva.top();
        stiva.pop();
        if(!vizitat[nod_curent]) {
            vector<int> ctc = vector<int>(0);
            DFS(grafTranspus, nod_curent, ctc, true);
            lista_ctc.push_back(ctc);
        }
    }
    ofstream fout("ctc.out");
    fout << lista_ctc.size() << '\n';
    for(const auto& ctc: lista_ctc) {
        for (auto nod: ctc)
            fout << nod << ' ';
        fout << '\n';
    }
    fout.close();
    return 0;
}