Cod sursa(job #3330691)

Utilizator boboc132Boboc Teodor boboc132 Data 21 decembrie 2025 12:29:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

// Pasul 1: DFS normal pentru a obtine ordinea terminarii nodurilor
void dfs1(int nod, const vector<vector<int>>& graf, vector<bool>& viz, vector<int>& stiva) {
    viz[nod]=true;
    for(auto vecin:graf[nod]){
        if(!viz[vecin]){
            dfs1(vecin,graf,viz,stiva);
        }
    }
    stiva.push_back(nod);
}

// Pasul 2: DFS pe graful INVERSAT pentru a extrage o componenta
void dfs2(int nod, const vector<vector<int>>& graf_inv, vector<bool>& viz, vector<int>& componenta_curenta) {
    viz[nod]=false;
    componenta_curenta.push_back(nod);
    for(auto vecin:graf_inv[nod]){
        if(viz[vecin]){
            dfs2(vecin,graf_inv,viz,componenta_curenta);
        }
    }
}

int main() {
    int n,m,x,y;
    in>>n>>m;

    vector<vector<int>> graf(n + 1);
    vector<vector<int>> graf_inv(n + 1);
    for (int i = 1; i <= m; i++) {
        in >> x >> y;
        graf[x].push_back(y);
        graf_inv[y].push_back(x); // AICI e secretul: inversam muchiile!
    }

    vector<bool> viz(n + 1, false);
    vector<int> stiva;

    // Pasul 1: Umplem stiva
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) 
            dfs1(i, graf, viz, stiva);
    }

    // Pasul 2: Procesam nodurile din stiva in ordine INVERSA (de la ultimul la primul)
    vector<vector<int>>toate_ctc;
    for(int i=stiva.size()-1;i>=0;i--){
        int nod=stiva[i];
        if(viz[nod]){
            vector<int>componenta;
            dfs2(nod,graf_inv,viz,componenta);
            toate_ctc.push_back(componenta);
        }
    }

    // Afisare
    out<<toate_ctc.size()<<"\n";
    for(auto ctc:toate_ctc){
        for(int nod:ctc){
            out<<nod<<" ";
        }
        out<<"\n";
    }
    return 0;
}