Cod sursa(job #3199445)

Utilizator AffectiveSmile2Mihnea Matea AffectiveSmile2 Data 1 februarie 2024 17:05:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX=100000;
int N,M,nrc;///nrc=nr comp tari conexe
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)///Tarjan
{
    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 unei CTC
    if(Dmin[x]==D[x])///x este radacina unei CTC
    {
        int u;
        nrc++;
        do ///Scoatem nodurile CTC de pe stiva
        {
            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;
}