Cod sursa(job #3374099)

Utilizator biancamihaiMihai Maria Bianca biancamihai Data 8 noiembrie 2026 17:50:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <bits/stdc++.h>
using namespace std;

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

    int nr_noduri, nr_arce;
    fin >> nr_noduri >> nr_arce;

    vector<vector<int>> lista_adiacenta(nr_noduri + 1);
    vector<vector<int>> lista_transpusa(nr_noduri + 1);
    for (int i = 0; i < nr_arce; i++) {
        int x, y;
        fin >> x >> y;
        lista_adiacenta[x].push_back(y);
        lista_transpusa[y].push_back(x);
    }

    vector<bool> vizitat(nr_noduri + 1, false);
    vector<int> urmatorul_vecin(nr_noduri + 1, 0);
    vector<int> ordine_terminare;

    for (int start = 1; start <= nr_noduri; start++) {
        if (vizitat[start]) continue;
        vector<int> stiva;
        stiva.push_back(start);
        vizitat[start] = true;

        while (!stiva.empty()) {
            int curent = stiva.back();
            if (urmatorul_vecin[curent] < (int)lista_adiacenta[curent].size()) {
                int vecin = lista_adiacenta[curent][urmatorul_vecin[curent]++];
                if (!vizitat[vecin]) {
                    vizitat[vecin] = true;
                    stiva.push_back(vecin);
                }
            } else {
                stiva.pop_back();
                ordine_terminare.push_back(curent);
            }
        }
    }
    vector<vector<int>> componente;
    vector<bool> vizitat_transpus(nr_noduri + 1, false);

    for (int i = nr_noduri - 1; i >= 0; i--) {
        int start = ordine_terminare[i];
        if (vizitat_transpus[start]) continue;

        vector<int> componenta;
        vector<int> stiva;
        stiva.push_back(start);
        vizitat_transpus[start] = true;

        while (!stiva.empty()) {
            int curent = stiva.back();
            stiva.pop_back();
            componenta.push_back(curent);
            for (int vecin : lista_transpusa[curent]) {
                if (!vizitat_transpus[vecin]) {
                    vizitat_transpus[vecin] = true;
                    stiva.push_back(vecin);
                }
            }
        }
        componente.push_back(componenta);
    }

    fout << componente.size() << "\n";
    for (const auto& componenta : componente) {
        for (int nod : componenta) fout << nod << " ";
        fout << "\n";
    }
    return 0;
}