Cod sursa(job #3371303)

Utilizator ilystefalexVaduva Stefan-Alexandru ilystefalex Data 29 octombrie 2026 17:37:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
//
// Created by Alex on 10/29/2026.
//

#include <iostream>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;
vector<vector<int>> adiacenta, transpus,ctc;
vector<bool> viz;
stack<int> st;
int n,m;
void citire() {
    ifstream fin("ctc.in");
    fin>>n>>m;
    adiacenta.resize(n+1);
    transpus.resize(n+1);
    viz.resize(n+1,0);
    for (int i=0;i<m;i++) {
        int nod,vecin;
        fin>>nod>>vecin;
        adiacenta[nod].push_back(vecin);
        transpus[vecin].push_back(nod);
    }


}

void dfs(int nod) {
    viz[nod]=true;
    for (int vecin: adiacenta[nod]) {
        if (!viz[vecin])
            dfs(vecin);

    }
    st.push(nod);


}
vector<int> comp;
void dfs2(int nod) {
    comp.push_back(nod);
    viz[nod]=true;
    for (int vecin: transpus[nod]) {
        if (!viz[vecin])
            dfs2(vecin);

    }



}

void rezolvare() {
    for (int i=1;i<=n ;i++) {
        if (!viz[i]) {
            dfs(i);
        }
    }
    fill(viz.begin(),viz.end(),0);
    while (!st.empty()) {
        if (!viz[st.top()]) {
            comp.clear();
            dfs2(st.top());
            ctc.push_back(comp);
        }
        st.pop();

    }

}

void afisare() {
    ofstream fout("ctc.out");
    fout<<ctc.size();
    for (int i=0;i<ctc.size();i++) {
        fout<<"\n";
        for (int j:ctc[i])
            fout<<j<<" ";

    }
}
int main(){
    citire();
    rezolvare();
    afisare();

}