Cod sursa(job #2863013)

Utilizator Seress26Seres Artur Seress26 Data 6 martie 2022 11:19:00
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 200001
///KOSORAJU.
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.in");
int n,m,nr,a,b;
vector <int> G[NMAX],GT[NMAX],CTC[NMAX];
int Vizitat[NMAX];
stack <int> S;
void Citire()
{
    f>>n;
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a;
        f>>b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
}
void DFSP(int Nod)
{
    int Vecin;
    Vizitat[Nod]=1;
    for(size_t i=0;i<G[Nod].size();i++)
    {
        Vecin=G[Nod][i];
        if(!Vizitat[Vecin])
            DFSP(Vecin);
    }
    S.push(Nod);
}
void DFSM(int Nod)
{
    int Vecin;
    Vizitat[Nod]=2;
    CTC[nr].push_back(Nod);
    for(size_t i=0;i<GT[Nod].size();i++)
    {
        Vecin=GT[Nod][i];
        if(Vizitat[Vecin]==1)
            DFSM(Vecin);
    }
}
void Rezolvare()
{
    int Nod;
    for(int i=1;i<=n;i++)
    {
        if(!Vizitat[i])
            DFSP(i);
    }
    while(!S.empty())
    {
        Nod=S.top();
        if(Vizitat[Nod]==1)
        {
            nr++;
            DFSM(Nod);
        }
        S.pop();
    }
}
void Afisare()
{
    g<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        for(size_t j=0;j<CTC[i].size();j++)
            g<<CTC[i][j]<<' ';
        g<<'\n';
    }
}
int main()
{
    Citire();
    Rezolvare();
    Afisare();

    return 0;
}