Cod sursa(job #3369404)

Utilizator IeremiaNicolaescu Ieremia Ieremia Data 20 octombrie 2026 10:26:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100005;

vector<int> g[NMAX], gt[NMAX]; 
vector<int> stiva, ctc[NMAX];  
bool viz[NMAX];
int n, m, nr_ctc;

void dfs1(int u) {
    viz[u] = true;
    for (int v : g[u]) {
        if (!viz[v]) dfs1(v);
    }
    stiva.push_back(u);
}

void dfs2(int u) {
    viz[u] = false; 
    ctc[nr_ctc].push_back(u);
    for (int v : gt[u]) {
        if (viz[v]) dfs2(v);
    }
}

int main() {
    fin >> n >> m;
    while (m--) {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y); 
        gt[y].push_back(x);  
    }
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) dfs1(i);
    }
    for (int i = stiva.size() - 1; i >= 0; i--) {
        int u = stiva[i];
        if (viz[u]) {
            nr_ctc++;
            dfs2(u);
        }
    }
    fout << nr_ctc << "\n";
    for (int i = 1; i <= nr_ctc; i++) {
        for (int v : ctc[i]) {
            fout << v << " ";
        }
        fout << "\n";
    }

    return 0;
}