Cod sursa(job #3374694)

Utilizator maria_5Diaconescu Maria maria_5 Data 9 noiembrie 2026 09:25:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int n,m;
const int NMAX = 100005;

vector<int> graf[NMAX];
vector<int> graf_transpus[NMAX];

bool vizitat1[NMAX];
bool vizitat2[NMAX];

vector<int> stiva;

vector<vector<int>> componente;

void dfs1(int nod) {
    vizitat1[nod] = true;

    for (int i = 0; i < (int)graf[nod].size(); i++) {
        int vecin = graf[nod][i];
        if (!vizitat1[vecin]) {
            dfs1(vecin);
        }
    }
    stiva.push_back(nod);
}

void dfs2(int nod, vector <int>& comp_curenta) {
    vizitat2[nod] = true;
    comp_curenta.push_back(nod);

    for (int i = 0; i < (int)graf_transpus[nod].size(); i++) {
        int vecin = graf_transpus[nod][i];
        if (!vizitat2[vecin]) {
            dfs2(vecin, comp_curenta);
        }
    }
}

int main () {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    cin>>n>>m;



    for (int i = 0; i < m; i++) {
        int u,v;
        cin >> u>>v;
        graf[u].push_back(v);
        graf_transpus[v].push_back(u);
    }

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

    }

    while (!stiva.empty()) {
        int nod=stiva.back();
        stiva.pop_back();

        if (!vizitat2[nod]) {
            vector<int> comp_noua;
            dfs2(nod, comp_noua);
            componente.push_back(comp_noua);
        }

    }

    cout << componente.size() << "\n";
    for (int i = 0; i < (int)componente.size(); i++) {
        for (int j = 0; j < (int)componente[i].size(); j++) {
            cout << componente[i][j] << (j + 1 == (int)componente[i].size() ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}