Cod sursa(job #3370049)

Utilizator viflaem2Granat Andrei Ionut viflaem2 Data 23 octombrie 2026 19:13:22
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<vector<int>> graf(100001);
vector<vector<int>> graf_inv(1000001);
vector<int> ordine;
vector<bool> vizitat(100001);
vector<bool> vizitatINV(100001);
vector<vector<int>> componente;
int n,m,index=-1;

void DFS(int i){
    vizitat[i]=1;
    for(int j=0;j<graf[i].size();j++){
        if(!vizitat[graf[i][j]]){
            DFS(graf[i][j]);
        }
    }
    ordine.push_back(i);
}

void DFS_inv(int i){
    vizitatINV[i]=1;
    componente[index].push_back(i);
    for(int j=0;j<graf_inv[i].size();j++){
        if(!vizitatINV[graf_inv[i][j]]){
            DFS_inv(graf_inv[i][j]);
        }
    }
}

int main()
{
f>>n>>m;
for(int i=0;i<=m-1;i++){
    int x,y; f>>x>>y;
    graf[x].push_back(y);
    graf_inv[y].push_back(x);
}
for(int i=1;i<=n;i++){
    if(!vizitat[i])
        DFS(i);
}
while(ordine.size()){
    int nod=ordine.back();
    ordine.pop_back();
    if(!vizitatINV[nod]){
        componente.emplace_back();
        index++;
        DFS_inv(nod);
    }
}
g<<index<<endl;
for(int i=0;i<=index;i++){
    for(int j=0;j<componente[i].size();j++){
        g<<componente[i][j]<<" ";
    }
    g<<endl;
}
return 0;
}