Cod sursa(job #3340298)

Utilizator TomMMMMatei Toma TomMMM Data 13 februarie 2026 16:31:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>

using namespace std;

int n;
vector<vector<int>> G, GT;
vector<bool> apar;
vector<int> term;

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

void read(){
    int m;
    fin >> n >> m;
    G = GT = vector<vector<int>> (n + 1);

    for(int i = 1; i <= m; i++){
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

}
void reset(){
    apar = vector<bool> (n + 1, 0);
}

void dfs(int nod){
    apar[nod] = 1;
    for(auto x: G[nod])
        if(!apar[x])
            dfs(x);
    term.push_back(nod);
}

vector<int> empty_vector;
vector<vector<int>> components;

void dfsT(int nod){
    apar[nod] = 1;
    for(auto x: GT[nod])
        if(!apar[x])
            dfsT(x);
    components.back().push_back(nod);
}


int main(){
    read();
    reset();
    for(int i = 1; i <= n; i++)
        if(!apar[i])
            dfs(i);

    reset();
    

    for(int i = term.size() - 1; i >= 0; i--)
        if(!apar[term[i]]){
            components.push_back(empty_vector);
            dfsT(term[i]);
        }
    fout << components.size() << '\n';
    for(vector<int> &c: components){
        for(int node: c) fout << node << ' ';
        fout << '\n';
    }
}