#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
using uint = unsigned int;
typedef struct {
uint nodSursa, nodDestinatie;
} muchie;
class graf {
public:
std::vector<std::vector<uint>> listaDeAdiacenta;
std::vector<uint> gradeInterioare;
graf(const std::vector<muchie> &muchii, const uint numarMuchii) {
listaDeAdiacenta.resize(numarMuchii + 1);
gradeInterioare = std::vector<uint>(numarMuchii + 1, 0);
for (auto &muchie : muchii) {
listaDeAdiacenta[muchie.nodSursa].push_back(muchie.nodDestinatie);
gradeInterioare[muchie.nodDestinatie]++;
}
}
void sortareTopologica(const uint numarMuchii,
std::vector<uint> &listaFinala) {
std::vector<uint> gradeInt = this->gradeInterioare;
std::vector<uint> S;
for (uint muchie = 0; muchie <= numarMuchii; muchie++) {
if (gradeInt[muchie] != 0)
S.push_back(muchie);
}
while (!S.empty()) {
uint nodCoada = S.back();
S.pop_back();
listaFinala.push_back(nodCoada);
for (uint m : this->listaDeAdiacenta[nodCoada]) {
gradeInt[nodCoada]--;
if (gradeInt[nodCoada] == 0)
gradeInt.push_back(m);
}
}
}
};
int main() {
std::ifstream inFile;
inFile.open("sortaret.in", std::ios::in);
if (inFile.is_open()) {
uint numarNoduri, numarArce;
inFile >> numarNoduri >> numarArce;
std::vector<muchie> muchii;
for (size_t arc = 0; arc < numarArce; arc++) {
muchie m;
inFile >> m.nodSursa >> m.nodDestinatie;
muchii.push_back(m);
}
graf graf(muchii, numarArce + 1);
std::vector<uint> listaFinala;
std::ofstream outFile;
outFile.open("sortaret.out", std::ios::out);
if (outFile.is_open()) {
graf.sortareTopologica(numarArce, listaFinala);
std::reverse(listaFinala.begin(), listaFinala.end());
for (auto nod : listaFinala)
outFile << nod << " ";
outFile.close();
} else {
std::cout << "Nu s-a putut scrie in fisier!" << std::endl;
}
} else {
std::cout << "Nu am putut deschide fisierul!" << std::endl;
}
inFile.close();
return 0;
}