Cod sursa(job #3374897)

Utilizator GabrielaTudoracheTudorache Gabriela GabrielaTudorache Data 9 noiembrie 2026 18:06:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<vector>
using namespace std;

vector<vector<int>> vecini;     
vector<vector<int>> invers;     
vector<bool> vizitat;           
vector<int> ordine;            
vector<int> componenta;         
vector<vector<int>> rezultat;   

void dfs1(int nod) {
    vizitat[nod] = true;
    for (int urm : vecini[nod]) {
        if (!vizitat[urm]) {
            dfs1(urm);
        }
    }
    ordine.push_back(nod);
}

void dfs2(int nod, int c) {
    componenta[nod] = c;
    rezultat[c].push_back(nod);
    for (int urm : invers[nod]) {
        if (componenta[urm] == 0) {
            dfs2(urm, c);
        }
    }
}

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int n, m;
    fin >> n >> m;

    vecini.resize(n + 1);
    invers.resize(n + 1);
    vizitat.assign(n + 1, false);
    componenta.assign(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        vecini[x].push_back(y);   
        invers[y].push_back(x);   
    }

    for (int v = 1; v <= n; v++) {
        if (!vizitat[v]) {
            dfs1(v);
        }
    }

    int nrComp = 0;
    rezultat.push_back(vector<int>());   
    for (int i = n - 1; i >= 0; i--) {
        int v = ordine[i];
        if (componenta[v] == 0) {
            nrComp++;
            rezultat.push_back(vector<int>());
            dfs2(v, nrComp);
        }
    }

    fout << nrComp << "\n";
    for (int c = 1; c <= nrComp; c++) {
        for (int v : rezultat[c]) {
            fout << v << " ";
        }
        fout << "\n";
    }
    return 0;
}