Cod sursa(job #3199443)

Utilizator biancaa_ungureanuUngureanu Bianca-Maria biancaa_ungureanu Data 1 februarie 2024 17:05:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 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]<==>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(auto &y:G[x])
    {
        if (D[y]==0) ///Muchie de arbore
        {
            DFS(y);
            Dmin[x]=min(Dmin[x],Dmin[y]);
        }
        else
        {
            if (inSt[y]==1) ///Muchie de intoarcere
                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 lui CTC
    if (Dmin[x]==D[x]) ///x este radacina unei CTC
    {
        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();
}