Cod sursa(job #3373733)

Utilizator Paul13Frincu Paul-Octavian Paul13 Data 7 noiembrie 2026 18:56:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.9 kb
// bibliotecile folosite
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

// fisierele din care citesc si scriu
ifstream fin("ctc.in");
ofstream fout("ctc.out");

// declar lista de adiacenta si lista inversa
vector<int> graf[100001]; // contine muchiile in directia originala
vector<int> invers[100001]; // contine muchiile in directia inversa

// vreau sa contorizez nodurile vizitate
bool vizitat[100001] = {};

// avem 3 vectori
vector<int> ordine; // rerine nodurile in ordinea terminarii primului dfs
vector<int> componenta; // retine nodurile componentei descoperite acum
vector<vector<int>> solutie; // retine toate componentele descoperite


// avem 2 functii dfs
// primul dfs("dfs1") doar parcurgem graful si retinem ordinea de terminare
void dfs1(int nod){
    vizitat[nod] = true; // setez nodul ca vizitat

    for(int vecin : graf[nod]){ // parcurg vecinii nodului
        if(!vizitat[vecin]){ // daca vecinul nu a fost vizitat
            dfs1(vecin); // il vizitez si pe el
        }
    }

    ordine.push_back(nod); // adaug nodul dupa ce am terminat
}

// al doilea dfs("dfs2") parcurgem graful invers si retinem componentele
void dfs2(int nod){
    vizitat[nod] = true; // setez nodul ca vizitat in a doua parcurgere

    componenta.push_back(nod); // adaug nod in componenta curenta

    for(int vecin : invers[nod]){ // exact ca la primul dfs
        if(!vizitat[vecin]){ // doar ca parcurg graful invers
            dfs2(vecin);
        }
    }
}

int main(){
    // citesc numarul de noduri si muchii
    int n, m;
    fin >> n >> m;

    // formez legarurile(lista de adiacenta pentru ambele grafuri)
    for(int i = 0; i < m; i++){
        int a, b;
        fin >> a >> b;

        graf[a].push_back(b);
        invers[b].push_back(a);
    }


    // parcurg toate nodurile pentru a ma asigura ca vizitez intreg graful
    for(int i = 1; i <= n; i++){ 
        if(!vizitat[i]){
            dfs1(i);
        }
    }

    // resetez vectorul vizitat pentru al doilea dfs
    for(int i = 1; i <= n; i ++){
        vizitat[i] = false;
    }

    // parcurg vectorul in ordine inversa
    for(int i = (int)ordine.size() - 1; i >= 0; i--){
        int nod = ordine[i]; // retin nodul curent

        if(!vizitat[nod]){ // daca nu a mai fost vizitat/ nu mai apare intr-o alta componenta
            componenta.clear(); // construiesc o componenta noua
            dfs2(nod); // si incep dfs-ul pe graful invers
            // dupa ce se termina dfs-ul in solutie adaug componenta rezultat
            solutie.push_back(componenta);
        }
    }

    fout << solutie.size() << '\n'; // afisez nr de componente tare conexe

    // si care sunt nodurile din fiecare componenta
    for(auto comp : solutie){
        for(int nod : comp){
            fout << nod << " ";
        }
        fout << '\n';
    }

    return 0;

}