Cod sursa(job #2795522)

Utilizator andreinovaNacu Andrei Emilian andreinova Data 6 noiembrie 2021 15:34:47
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 100001;

ifstream in("ctc.in");
ofstream out("ctc.out");

vector <int> AdiacentaT[MAX];
vector <int> componente;

class Graf
{
    int nrNoduri;
    stack <int> Stiva;
    bool Vizitat[MAX] = {0};
    bool VizitatT[MAX] = {0};

public:
    vector <int> Adiacenta[MAX];

    Graf(int nrNoduri);

    void UmpleStiva(int nod);
    void Transpus();
    void Parcurgere();
    void DfsT(int nod);
    void Ctc();
};

Graf :: Graf(int nrNoduri)
{
    this->nrNoduri = nrNoduri;
}

void Graf :: Transpus()
{
    for(int i = 1; i <= nrNoduri; ++i)
        for(auto j : Adiacenta[i])
            AdiacentaT[j].push_back(i);
}

void Graf :: UmpleStiva(int nod)
{
    VizitatT[nod] = 1;

    for(auto i : Adiacenta[nod])
        if(!VizitatT[i])
            UmpleStiva(i);

    Stiva.push(nod);
}

void Graf :: Parcurgere()
{
    for(int i = 1; i <= nrNoduri; ++i)
        if(!VizitatT[i])
            UmpleStiva(i);
}

void Graf :: DfsT(int nod)
{
    Vizitat[nod] = 1;
    componente.push_back(nod);
    for(auto i : AdiacentaT[nod])
        if(!Vizitat[i])
            DfsT(i);
}

void Graf :: Ctc()
{
    int total = 0;

    while(!Stiva.empty())
    {
        int nod = Stiva.top();
        Stiva.pop();

        if(!Vizitat[nod])
        {
            total++;
            DfsT(nod);
            componente.push_back(-1);
        }
    }

    out << total << endl;

    for(int i = 0; i < componente.size(); i++)
        if(componente[i] == -1)
            out << endl;
        else
            out << componente[i] << " ";
}

int main()
{
    int N, M;
    in >> N >> M;
    Graf g(N);

    for(int i = 1; i <= M; ++i)
    {
        int nod1, nod2;
        in >> nod1 >> nod2;
        g.Adiacenta[nod1].push_back(nod2);
    }
    g.Transpus();
    g.Parcurgere();
    g.Ctc();

    return 0;
}