Cod sursa(job #3374122)

Utilizator MrbgdBogdan Mrbgd Data 8 noiembrie 2026 18:32:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.39 kb
#include <fstream>
#include <vector>

using namespace std;

vector<int> ordine_de_finalizare(const vector<vector<int>>& graf) {
    vector<char> vizitat(graf.size(), false);
    vector<size_t> urmator(graf.size());
    vector<int> ordine;
    vector<int> stiva;
    ordine.reserve(graf.size() - 1);
    stiva.reserve(graf.size() - 1);

    for (int start = 1; start < static_cast<int>(graf.size()); ++start) {
        if (vizitat[start]) {
            continue;
        }

        vizitat[start] = true;
        stiva.push_back(start);
        while (!stiva.empty()) {
            int nod = stiva.back();
            if (urmator[nod] == graf[nod].size()) {
                ordine.push_back(nod);
                stiva.pop_back();
            } else {
                int vecin = graf[nod][urmator[nod]++];
                if (!vizitat[vecin]) {
                    vizitat[vecin] = true;
                    stiva.push_back(vecin);
                }
            }
        }
    }
    return ordine;
}

int main() {
    ifstream intrare("ctc.in");
    ofstream iesire("ctc.out");

    int n, m;
    intrare >> n >> m;
    vector<vector<int>> graf(n + 1);
    vector<vector<int>> transpus(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y;
        intrare >> x >> y;
        graf[x].push_back(y);
        transpus[y].push_back(x);
    }

    vector<int> ordine = ordine_de_finalizare(graf);
    vector<char> vizitat(n + 1, false);
    vector<int> stiva;
    vector<vector<int>> componente;
    for (auto it = ordine.rbegin(); it != ordine.rend(); ++it) {
        int start = *it;
        if (vizitat[start]) {
            continue;
        }

        componente.emplace_back();
        auto& componenta = componente.back();
        stiva.push_back(start);
        vizitat[start] = true;
        while (!stiva.empty()) {
            int nod = stiva.back();
            stiva.pop_back();
            componenta.push_back(nod);
            for (int vecin : transpus[nod]) {
                if (!vizitat[vecin]) {
                    vizitat[vecin] = true;
                    stiva.push_back(vecin);
                }
            }
        }
    }

    iesire << componente.size() << '\n';
    for (const auto& componenta : componente) {
        for (size_t i = 0; i < componenta.size(); ++i) {
            if (i != 0) {
                iesire << ' ';
            }
            iesire << componenta[i];
        }
        iesire << '\n';
    }
}