Cod sursa(job #3376242)

Utilizator Buzoianu_RobertBuzoianu Mircea Robert Buzoianu_Robert Data 16 noiembrie 2026 21:50:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void dfs1(int u,const vector<vector<int>> &graf,vector<int> &viz,vector<int>&ordine){
    viz[u]=1;
    for(auto v : graf[u]){
        if(viz[v]==0){
            dfs1(v,graf,viz,ordine);
        }
    }
    ordine.push_back(u);

}
void dfs2(int u,const vector<vector<int>>&grafInv,vector<int>&comp,int nrComp){
    comp[u]=nrComp;
    for(auto v : grafInv[u]){
        if(comp[v]==0){
            dfs2(v,grafInv,comp,nrComp);
        }
    }
}

int main(){
    int n,m;
    if(!fin.is_open()){
        cout<<"Nu s-a putut deschide fisierul";
        return 0;
    }
    fin>>n>>m;
    vector<vector<int>> graf(n+1);
    vector<vector<int>> grafInv(n+1);
    for(int k=1;k<=m;k++){
        int i,j;
        fin>>i>>j;
        graf[i].push_back(j);
        grafInv[j].push_back(i);
    }
    vector<int>viz(n+1,0);
    vector<int>ordine;

    for(int i=1;i<=n;i++){
        if(viz[i]==0){
            dfs1(i,graf,viz,ordine);
        }
    }
    vector<int>comp(n+1,0);
    int nrComp=0;
    for(int i=(int)ordine.size()-1;i>=0;i--){
        int u=ordine[i];
        if(comp[u]==0){
            nrComp++;
            dfs2(u, grafInv, comp, nrComp);
        }
    }
    fout<<nrComp<<endl;
    vector<vector<int>>componente(n+1);
    for(int i=1;i<=n;i++){
        componente[comp[i]].push_back(i);
    }
    for(int i=1;i<=nrComp;i++){
        for(auto v : componente[i]){
            fout<<v<<" ";
        }
        fout<<endl;
    }
}