Cod sursa(job #3322645)

Utilizator Mateixx1Trandafir Matei Mateixx1 Data 15 noiembrie 2025 10:12:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100000;
int N, M, nrc;

vector<int> G[NMAX + 1], CTC[NMAX + 1];
int D[NMAX + 1], Dmin[NMAX + 1], Timp = 0;

stack<int> S;
bool inSt[NMAX + 1]; ///inSt[i] = 1 <==> i este in stiva

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

void citire() {
    int x, y;
    f >> N >> M;
    for(int i = 1; i <= M; i++) {
        f >> x >> y;
        G[x].push_back(y);
    }
}

void DFS(int x) {
    D[x]=++Timp;
    Dmin[x]=D[x];
    S.push(x);
    inSt[x]=1;
    for(const auto&y:G[x]) {
        if(D[y]==0) { ///muhcie de arbore
            DFS(y);
            Dmin[x]=min(Dmin[x],Dmin[y]);
        } else {
            if(inSt[y]==1) {
                Dmin[x]=min(Dmin[x],D[y]);
            }
        }
    }
    if(Dmin[x]==D[x]) {
        int u;
        nrc++;
        do {
            u=S.top();
            CTC[nrc].push_back(u);
            S.pop();
            inSt[u]=0;
        } while(x!=u);
    }
}


void afisare() {
    g<<nrc<<'\n';
    for(int i=1; i<=nrc; i++) {
        for(const auto&x:CTC[i]) {
            g<<x<<' ';
        }
        g<<'\n';
    }
}


int main() {
    citire();
    for(int i=1; i<=N; i++) {
        if(D[i]==0) {
            DFS(i);
        }
    }
    afisare();
    f.close();
    g.close();
    return 0;
}