Cod sursa(job #2573555)

Utilizator copanelTudor Roman copanel Data 5 martie 2020 18:08:08
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>

std::vector<int> arce[100001];
std::vector<int> transpus[100001];
std::vector<std::vector<int>> componente;
std::vector<int> sort;
bool vazut[100001];
bool vazut2[100001];

void sortare_topologica(int nod) {
    vazut[nod] = true;
    for (const int succ : arce[nod]) {
        if (!vazut[succ]) {
            sortare_topologica(succ);
        }
    }
    sort.push_back(nod);
}

void dfs2(int nod, std::vector<int>& r) {
    vazut2[nod] = true;
    r.push_back(nod);
    for (const int succ : transpus[nod]) {
        if (!vazut2[succ]) {
            dfs2(succ, r);
        }
    }
}

int main() {
    std::ifstream fin("ctc.in");
    std::ofstream fout("ctc.out");
    int n, m;

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        arce[a].push_back(b);
        transpus[b].push_back(a);
    }

    sortare_topologica(1);
    for (int i = sort.size() - 1; i >= 0; i--) {
        if (!vazut2[sort[i]]) {
            componente.push_back({});
            dfs2(sort[i], componente.back());
        }
    }
    fout << componente.size() << '\n';
    for (const auto& c : componente) {
        for (const int x : c) {
            fout << x << ' ';
        }
        fout << '\n';
    }
    return 0;
}