#include <fstream>
#include <iostream>
#include <list>
#include <queue>
#include <string>
#include <utility>
class Graf {
private:
unsigned int numarNoduri;
std::list<int> *l;
public:
Graf(unsigned int _numarNoduri) : numarNoduri(_numarNoduri) {
l = new std::list<int>[numarNoduri];
}
void adaugaNod(unsigned int nodInceput, unsigned int nodSfarsit) {
l[nodInceput].push_back(nodSfarsit);
}
void sortareTopologica() {
int *gradeInterioare = new int[numarNoduri]{0};
for (size_t i = 0; i < numarNoduri; i++) {
for (auto it = l[i].begin(); it != l[i].end(); it++)
gradeInterioare[*it]++;
}
std::queue<unsigned int> coada;
for (size_t i = 0; i < numarNoduri; i++)
if (gradeInterioare[i] == 0)
coada.push(i);
while (!coada.empty()) {
}
}
};
int main() {
std::ifstream inFile;
inFile.open("sortaret.in", std::ios::in);
if (inFile.is_open()) {
unsigned int numarNoduri, numarLinii;
inFile >> numarNoduri >> numarLinii;
std::list<unsigned int> *l = new std::list<unsigned int>[numarNoduri + 1];
unsigned int nodInceput, nodSfarsit;
for (size_t linie = 0; linie < numarLinii; linie++) {
inFile >> nodInceput >> nodSfarsit;
l[nodInceput].push_back(nodSfarsit);
}
unsigned int *gradInterior = new unsigned int[numarNoduri]{0};
// iterate over all edges
for (size_t nod = 0; nod < numarNoduri; nod++) {
for (auto it = l[nod].begin(); it != l[nod].end(); it++) {
gradInterior[*it]++;
}
}
std::queue<int> coadaNoduri;
for (size_t nod = 0; nod < numarNoduri; nod++) {
if (gradInterior[nod] == 0) {
coadaNoduri.push(nod);
}
}
std::ofstream outFile;
outFile.open("sortaret.out", std::ios::out);
if (outFile.is_open()) {
while (!coadaNoduri.empty()) {
int f = coadaNoduri.front();
outFile << ((f != 0) ? (std::to_string(f) + " ") : (""));
coadaNoduri.pop();
for (auto it = l[f].begin(); it != l[f].end(); it++) {
gradInterior[*it]--;
if (gradInterior[*it] == 0) {
coadaNoduri.push(*it);
}
}
}
outFile.close();
} else
std::cout << "Nu s-a putut scrie in fisier!" << std::endl;
inFile.close();
} else
std::cout << "Nu am putut deschide fisierul!" << std::endl;
return 0;
}