Cod sursa(job #3373941)

Utilizator Alexandru6041Alexandru Chelariu Alexandru6041 Data 8 noiembrie 2026 11:57:03
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>

int n, m;
std::vector < std::vector <int> > graf, graf_inversat, ctc;
std::vector <bool> viz;
std::vector <int> ordine;

void dfs1(int u) {
    viz[u] = true;
    for(int w : graf[u])
        if(!viz[w])
            dfs1(u);
    
    ordine.push_back(u);
}


void dfs2(int u, std::vector<int> &comp) {
    viz[u] = true;
    comp.push_back(u);
    for(int w : graf_inversat[u])
        if(!viz[w])
            dfs2(w, comp);
}

int main() {
    std::ifstream in("ctc.in");
    in >> n >> m;
    
    graf.assign((n + 1), {});
    graf_inversat.assign(n + 1, {});

    for(int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;

        graf_inversat[y].push_back(x);
        graf[x].push_back(y);    
    }
    in.close();

    viz.assign(n + 1, false);
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs1(i);
    
    viz.assign(n + 1, false);
    for(int i = (int) ordine.size() - 1; i >= 0; i--) {
        int u = ordine[i];
        if(!viz[u]) {
            std::vector <int> comp;
            dfs2(u, comp);
            ctc.push_back(comp);
        }
    }

    std::ofstream out("ctc.out");
    out << (int) ctc.size() << '\n';
    for(auto &c : ctc) {
        for(int x : c)
            out << x << ' ';
        out<<'\n';    
    }

    out.close();
    return 0;
}