Cod sursa(job #3372387)

Utilizator yolanqaStefanescu Yolanda - Gabriela yolanqa Data 3 noiembrie 2026 15:05:22
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <fstream>

std::vector<std::vector<int>> graf;
std::vector<std::vector<int>> graf_transpus;
std::vector<int> vizitat;
std::vector<int> stiva;
std::vector<int> componenta;



void dfs(int nod){
    vizitat[nod]=1;
    for(int vecin : graf[nod])
        if(!vizitat[vecin])
            dfs(vecin);

    stiva.push_back(nod);

}

void dfs_transpus(int nod){
    vizitat[nod] = 1;
    componenta.push_back(nod);

    for(int i : graf_transpus[nod])
        if(!vizitat[i])
            dfs(i);

}



int main(){

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

    int n, m;
    if(!(fin>>n>>m))
        return 0;

    graf.resize(n+1);
    vizitat.resize(n+1, 0);
    graf_transpus.resize(n+1);

    for(int i = 0;i<m;i++){
        int x, y;
        fin>>x>>y;
        graf[x].push_back(y);
        graf_transpus[y].push_back(x);
    }
    
    
    for(int i =1;i<=n;i++)
        if(!vizitat[i])
            dfs(i);

    
    
    vizitat.resize(n + 1, 0);
    
    
    for(int i = stiva.size() - 1; i >= 0; i--) {
        int nod = stiva[i];
        if(!vizitat[nod]) {
            componenta.clear(); //goleste vect pt noua comp
            dfs_transpus(nod);
            toate_componentele.push_back(componenta);
        }
    }
    
    
    fout << toate_componentele.size() << "\n";
    for(const auto& ctc : toate_componentele) {
        for(int nod : ctc) {
            fout << nod << " ";
        }
        fout << "\n";
    }

    return 0;
}