Cod sursa(job #3374665)

Utilizator fanceapaMosul Tudor fanceapa Data 9 noiembrie 2026 08:53:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");

vector < vector <int> > muchii, muchiiInverse, componente;
vector <bool> vizitat;
vector <int> ordine;

void dfs(int nod){
    vizitat[nod] = true;
    for (auto vecin : muchii[nod]){
        if (!vizitat[vecin]){
            dfs(vecin);
        }
    }
    ordine.push_back(nod);
}

void dfsInvers(int nod){
    vizitat[nod] = false;
    componente.back().push_back(nod);
    for (auto vecin : muchiiInverse[nod]){
        if (vizitat[vecin]){
            dfsInvers(vecin);
        }
    }
}

int main(){
    int N, M;
    fin >> N >> M;
    muchii.resize(N + 1);
    muchiiInverse.resize(N + 1);
    vizitat.resize(N + 1, false);
    for (int i = 0; i < M; i++){
        int x, y;
        fin >> x >> y;
        muchii[x].push_back(y);
        muchiiInverse[y].push_back(x);
    }

    for (int i = 1; i <= N; i++){
        if (!vizitat[i]){
            dfs(i);
        }
    }
    for (int i = N - 1; i >= 0; i--){
        if (vizitat[ordine[i]]){
            componente.push_back(vector <int> ());
            dfsInvers(ordine[i]);
        }
    }

    fout << componente.size() << "\n";
    for (int i = 0; i < componente.size(); i++){
        for (auto nod : componente[i]){
            fout << nod << " ";
        }
        fout << "\n";
    }
    return 0;
}