Cod sursa(job #3372391)

Utilizator yolanqaStefanescu Yolanda - Gabriela yolanqa Data 3 noiembrie 2026 15:17:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <vector>
#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;
std::vector<std::vector<int>> toate_componentele;





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 vecin : graf_transpus[nod]) {
        if(!vizitat[vecin]) {
            dfs_transpus(vecin); 
        }
    }}




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);
    graf_transpus.resize(n + 1);
    vizitat.assign(n + 1, 0); 

    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.assign(n + 1, 0);
    
    for(int i = stiva.size() - 1; i >= 0; i--) {
        int nod = stiva[i];

        if(!vizitat[nod]) {
            componenta.clear(); 
            dfs_transpus(nod); 
            
            
            std::sort(componenta.begin(), componenta.end());
            
            toate_componentele.push_back(componenta);
        }
    }
    

    std::sort(toate_componentele.begin(), toate_componentele.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return a[0] < b[0];
    });
    

    fout << toate_componentele.size() << "\n";

    for(const auto& ctc : toate_componentele) {
        for(int nod : ctc) {
            fout << nod << " ";
        }
        fout << "\n";
    }

    return 0;
}