Cod sursa(job #3268946)

Utilizator ioanabaduIoana Badu ioanabadu Data 18 ianuarie 2025 09:49:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

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

void dfsGraph (int x){
    if (viz[x])
        return;
    viz[x] = true;

    for (auto idx:graph[x]){
        dfsGraph(idx);
    }
    stiva.push_back(x);
}

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

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

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] == false)
            dfsGraph(i);
    }

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

    for (int i=stiva.size()-1; i>=0; --i){
        if (viz[stiva[i]] == false){
            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;
}