Pagini recente » Cod sursa (job #1952273) | Cod sursa (job #1706912) | Cod sursa (job #1424468) | Cod sursa (job #1712844) | Cod sursa (job #2797784)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class Graf
{
private:
int numar_noduri, numar_muchii;
vector <int> lista_adiacenta[10001];
public:
void sortare_topologica();
void citire();
void functie(int nod, int vizitare[], stack <int> &stiva);
};
/// citire
void Graf :: citire()
{
int capat_stang, capat_drept;
fin >> numar_noduri >> numar_muchii;
for(int i = 0; i < numar_muchii; i++)
{
fin >> capat_stang >> capat_drept;
lista_adiacenta[capat_stang].push_back(capat_drept);
}
}
/// sortare topologica
void Graf :: sortare_topologica()
{
stack <int> stiva;
int vizitare[numar_noduri + 1] = {0};
for(int i = 1; i <= numar_noduri; i++)
if(!vizitare[i])
functie(i, vizitare, stiva);
while(!stiva.empty())
{
fout << stiva.top() << " ";
stiva.pop();
}
}
/// functie
void Graf :: functie(int nod, int vizitare[], stack <int> &stiva)
{
vizitare[nod] = 1;
for(int i = 0; i < lista_adiacenta[nod].size(); i++)
if(!vizitare[lista_adiacenta[nod][i]])
functie(lista_adiacenta[nod][i], vizitare, stiva);
stiva.push(nod);
}
int main()
{
Graf x;
x.citire();
x.sortare_topologica();
fin.close();
fout.close();
return 0;
}