Cod sursa(job #2793653)

Utilizator andreinovaNacu Andrei Emilian andreinova Data 3 noiembrie 2021 20:55:58
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 100001;

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

/*
ifstream in("bfs.in");
ofstream out("bfs.out");
*/

/*
ifstream in("dfs.in");
ofstream out("dfs.out");
*/

/*
ifstream in("hakimi.in");
ofstream out("hakimi.out");
*/

class Graf
{
    int NrNoduri;
    vector<int> Adiacenta[MAX];
    bool Vizitat[MAX] = {0};
    stack<int> Stiva;
public:

    Graf(int NrNoduri);

    void AdaugaMuchie(int nod, int nodConectat);

    void DfsT(int nod);
    void Sortare_Topologica();
};

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

void Graf::AdaugaMuchie(int nod, int nodConectat)
{
    Adiacenta[nod].push_back(nodConectat);
}


void Graf::DfsT(int nod)
{
    Vizitat[nod] = 1;

    for (auto i: Adiacenta[nod])
        if (!Vizitat[i])
        {
            DfsT(i);
        }

    Stiva.push(nod);
}

void Graf::Sortare_Topologica ()
{
    for(int i = 1; i <= NrNoduri; i++)
        if(!Vizitat[i])
        {
            DfsT(i);
        }

    while (!Stiva.empty())
    {
        out << Stiva.top() << " ";
        Stiva.pop();
    }
}
int main()
{
    int N, M;
    in >> N >> M;

    int nod1, nod2;
    Graf g(N);
    for(int i = 0; i < M; i++)
    {
        in >> nod1 >> nod2;
        g.AdaugaMuchie(nod1, nod2);
    }

    g.Sortare_Topologica();

    return 0;
}