Cod sursa(job #2703293)

Utilizator balintfranceskaBalint Franceska balintfranceska Data 7 februarie 2021 22:56:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include    <fstream>
#include    <vector>
#include    <stack>
using namespace std;
ifstream f("ctc.in"); ofstream g("ctc.out");
stack <int> S;
vector <int> G[100005],GT[100005],CTC[100005];
int N, M, NrCTC, viz[100005];
void citire()
{   f>>N>>M;
    for(int i=1; i<=M; ++i)
    {   int x, y;
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}
void DFSP(int Nod)
{   viz[Nod]=1;
    for(unsigned int i=0; i<G[Nod].size(); ++i)
    {   int Vecin=G[Nod][i];
        if(!viz[Vecin]) DFSP(Vecin);
    }
    S.push(Nod);
}
void DFSM(int Nod)
{   viz[Nod]=2;
    CTC[NrCTC].push_back(Nod);
    for(unsigned int i=0; i<GT[Nod].size(); ++i)
    {   int Vecin=GT[Nod][i];
        if(viz[Vecin]==1) DFSM(Vecin);
    }
}
void rez()
{   for(int i=1; i<=N; ++i)
        if(!viz[i]) DFSP(i);
    while(!S.empty())
    {   int Nod=S.top();
        if(viz[Nod]==1)
        {   NrCTC++;
            DFSM(Nod);
        }
        S.pop();
    }
}
void scriere()
{   g<<NrCTC<<'\n';
    for(int i=1; i<=NrCTC; ++i)
    {   for(unsigned int j=0; j<CTC[i].size(); ++j) g<<CTC[i][j]<<' ';
        g<<'\n';
    }
}

int main()
{    citire();
    rez();
    scriere();
    f.close(); g.close(); return 0;
}