Cod sursa(job #3341833)

Utilizator ioanabaduIoana Badu ioanabadu Data 21 februarie 2026 12:27:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005

using namespace std;

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

vector <int> graph[NMAX], trans[NMAX], ctc[NMAX];
vector <int> stiva;
int nodes, edges, numCtc;
bool viz[NMAX];

void dfs (int idx){
    if (viz[idx])
        return;
    viz[idx] = true;
    
    for (auto neigh:graph[idx])
        dfs(neigh);
    stiva.push_back(idx);
}

void dfsTrans (int idx){
    if (viz[idx])
        return;
    viz[idx] = true;
    ctc[numCtc].push_back(idx);

    for (auto neigh:trans[idx])
        dfsTrans(neigh);
}

int main (){
    int x, y;

    in >> nodes >> edges;
    for (int i=1; i<=edges; ++i){
        in >> x >> y;
        graph[x].push_back(y);
        trans[y].push_back(x);
    }

    for (int i=1; i<=nodes; ++i)
        if (!viz[i]) dfs(i);

    for (int i=1; i<=nodes; ++i)
        viz[i] = false;

    for (int i=stiva.size()-1; i>=0; --i){
        if (!viz[stiva[i]]){
            dfsTrans(stiva[i]);
            numCtc++;
        }
    }

    out << numCtc << '\n';
    for (int i=0; i<numCtc; ++i){
        for (auto idx:ctc[i])
            out << idx << ' ';
        out << '\n';
    }

    return 0;
}