Cod sursa(job #2810152)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 28 noiembrie 2021 17:40:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
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];
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(auto &y:G[x]) {
        if(D[y]==0) {
            DFS(y);
            Dmin[x]=min(Dmin[x],Dmin[y]);
        } else {
            if(inSt[y]==1)///muchie de intoarecere
                Dmin[x]=min(Dmin[x],D[y]);
            ///altfel este o muchie inainte sau muchie cross catre alta componenta conexa

        }
    }
    ///Daca x nu poate urca mai sus de x, atunci el este radacina unei CTC
    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(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;
}