Cod sursa(job #3347760)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 18 martie 2026 11:12:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 1e5 + 1;

int n, m, timp;

bool inst[NMAX];
int nma[NMAX], d[NMAX];

stack<int> s;
vector<int> G[NMAX];
vector<vector<int>> CTC;

void citire() {
    fin >> n >> m;
    for(int i = 1, x, y; i <= m; ++i) {
        fin >> x >> y;
        G[x].push_back(y);
    }
}

void dfs(int x) {
    d[x] = ++timp;
    nma[x] = timp;

    inst[x] = 1;
    s.push(x);

    for(const auto& y : G[x]) {
        if(d[y] == 0) {
            dfs(y);
            nma[x] = min(nma[x], nma[y]);
        } else if(inst[y]) {
            nma[x] = min(nma[x], d[y]);
        }
    }

    if(nma[x] != d[x]) return;

    CTC.push_back(vector<int>());
    int y;

    do {
        y = s.top();
        s.pop();
        CTC.back().push_back(y);
        inst[y] = 0;
    } while(y != x);
}

void afis() {
    fout << CTC.size() << '\n';
    for(const auto& v : CTC) {
        for(const auto& x : v) {
            fout << x << ' ';
        }
        fout << '\n';
    }
}

int main() {
    citire();
    for(int i = 1; i <= n; ++i) {
        if(d[i] == 0) dfs(i);
    }
    afis();
    return 0;
}