Cod sursa(job #3343391)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 27 februarie 2026 12:06:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <stack>
#include <vector>
#include <set>

using namespace std;

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

const int NMAX = 1e5 + 1;

int n, m, timp, nrCtc;

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

vector<int> G[NMAX],  CTC[NMAX];
stack<int> st;

void citire() {
    int x, y;

    fin >> n >> m;

    while(m--) {
        fin >> x >> y;

        G[x].push_back(y);
    }
}

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

    st.push(x);
    inSt[x] = 1;

    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(d[x] == nma[x]) {
        int y;

        ++nrCtc;

        do {
            y = st.top();
            st.pop();

            CTC[nrCtc].push_back(y);

            inSt[y] = 0;
        } while(y != x);
    }
}

void afisare() {
    fout << nrCtc << '\n';

    for(int i = 1; i <= nrCtc; ++i) {
        for(const auto& x : CTC[i]) {
            fout << x << ' ';
        }

        fout << '\n';
    }
}

int main() {
    citire();

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

    afisare();
    return 0;
}