Cod sursa(job #3341832)

Utilizator ioanabaduIoana Badu ioanabadu Data 21 februarie 2026 12:23:13
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 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, viz[NMAX];

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

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=nodes-1; i>=0; --i){
        if (!viz[stiva[i]]){
            numCtc++;
            dfsTrans(stiva[i]);
        }
    }

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

    return 0;
}