Cod sursa(job #3334436)

Utilizator flaviusstefflavius stefan flaviusstef Data 17 ianuarie 2026 16:57:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> nod_vec(1e6);
vector<vector<int>> nod_vecT(1e6);
vector<int>viz(1e6,0),viz2(1e6,0);
vector<vector<int>> comp_conex;
vector<int> componenta;
stack<int> st;
void dfs(int i) {
    viz[i]=1;
    for (auto j : nod_vec[i]) {
        if (viz[j]==0) {
            dfs(j);
        }
    }
    st.push(i);
}
void dfsT(int i) {
    viz2[i] = 1;
    componenta.push_back(i);
    for (auto j : nod_vecT[i]) {
        if (viz2[j]==0) {
            dfsT(j);
        }
    }
}
int main() {
    int n, m;
    fin>>n>>m;
    for (int i=1;i<=m;i++) {
        int a, b;
        fin>>a>>b;
        nod_vec[a].push_back(b);
        nod_vecT[b].push_back(a);
    }
    for (int i=1;i<=n;i++) {
        if (viz[i]==0) {
            dfs(i);
        }
    }
    while (st.size()!=0) {
        int curent = st.top();
        st.pop();
        if (viz2[curent]==0) {
            componenta.clear();
            dfsT(curent);
            comp_conex.push_back(componenta);
        }
    }
    fout<<comp_conex.size()<<endl;
    for (int i=0;i<=comp_conex.size()-1;i++) {
        for (auto j : comp_conex[i]) fout<<j<<" ";
        fout<<endl;
    }
    return 0;
}