Cod sursa(job #3374221)

Utilizator TomikeToma Rares Tomike Data 8 noiembrie 2026 20:51:04
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
using namespace std;

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

int n, m;
vector<int> g[100005], gt[100005];
bool viz1[100005], viz2[100005];
vector<int> ordine;
vector<vector<int>> comp;

void dfs1(int u){
    viz1[u] = 1;
    for(int v : g[u]){
        if(!viz1[v]) dfs1(v);
    }
    ordine.push_back(u);
}

void dfs2(int u){
    viz2[u] = 1;
    comp.back().push_back(u);
    for(int v : gt[u]){
        if(!viz2[v]){
            dfs2(v);
        }
    }
}

int main(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for(int i = 1; i <= n; i++){
        if(!viz1[i]) dfs1(i);
    }

    for(int i = n - 1; i >= 0; i--){
        int u = ordine[i];
        if(!viz2[u]){
            comp.push_back(vector<int>());
            dfs2(u);
        }
    }

    fout << comp.size() << endl;
    for(auto &c : comp){
        for(int x : c) fout << x << ' ';
    }
    fout << endl;
}