Cod sursa(job #3374350)

Utilizator luizaaaDutu Luiza-Alexandra luizaaa Data 8 noiembrie 2026 23:13:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAX_NODURI = 100005;

vector<int> graf_normal[MAX_NODURI];
vector<int> graf_inversat[MAX_NODURI];

bool vizitat[MAX_NODURI];

vector<int> ordine_terminare; 

vector<int> componenta_curenta;

vector<vector<int>> toate_componentele;

void dfs_prima_parcurgere(int nod) {
    vizitat[nod] = true;
    
    for (int vecin : graf_normal[nod]) {
        if (!vizitat[vecin]) {
            dfs_prima_parcurgere(vecin);
        }
    }
    ordine_terminare.push_back(nod);
}


void dfs_a_doua_parcurgere(int nod) {
    vizitat[nod] = true;
    componenta_curenta.push_back(nod);
    
    for (int vecin : graf_inversat[nod]) {
        if (!vizitat[vecin]) {
            dfs_a_doua_parcurgere(vecin);
        }
    }
}


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

    int numar_noduri, numar_muchii;
    fin >> numar_noduri >> numar_muchii;

    for (int i = 0; i < numar_muchii; ++i) {
        int nod_start, nod_destinatie;
        fin >> nod_start >> nod_destinatie;
        
        graf_normal[nod_start].push_back(nod_destinatie);

        graf_inversat[nod_destinatie].push_back(nod_start);
    }

    for (int i = 1; i <= numar_noduri; ++i) {
        if (!vizitat[i]) {
            dfs_prima_parcurgere(i);
        }
    }

    for (int i = 1; i <= numar_noduri; ++i) {
        vizitat[i] = false;
    }

    for (int i = numar_noduri - 1; i >= 0; --i) {
        int nod = ordine_terminare[i];
        
        if (!vizitat[nod]) {
            componenta_curenta.clear(); 

            dfs_a_doua_parcurgere(nod); 

            toate_componentele.push_back(componenta_curenta);
        }
    }
    
    fout << toate_componentele.size() << "\n";
    for (const auto& componenta : toate_componentele) {
        for (int nod : componenta) {
            fout << nod << " ";
        }
        fout << "\n";
    }

    return 0;
}