#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using uint = unsigned int;
uint viziteaza(const std::vector<std::vector<bool>> &matriceAdiacenta,
std::vector<bool> &vizitat, std::vector<uint> &ordine,
uint index, uint nod) {
if (vizitat[nod] == true)
return index;
vizitat[nod] = true;
for (size_t vecin = 0; vecin < matriceAdiacenta.size(); vecin++) {
if (matriceAdiacenta[nod][vecin] != false && !vizitat[vecin])
index = viziteaza(matriceAdiacenta, vizitat, ordine, index, vecin);
}
ordine[index--] = nod;
return index;
}
std::vector<uint>
sortareTopologica(const std::vector<std::vector<bool>> &matriceAdiacenta) {
uint numarNoduri = matriceAdiacenta.size();
std::vector<bool> vizitat(numarNoduri, false);
std::vector<uint> ordine(numarNoduri, 0);
uint index = numarNoduri - 1;
for (size_t nod = 0; nod < numarNoduri; nod++) {
if (!vizitat[nod])
index = viziteaza(matriceAdiacenta, vizitat, ordine, index, nod);
}
return ordine;
}
int main() {
std::ifstream inFile;
inFile.open("sortaret.in", std::ios::in);
if (inFile.is_open()) {
int numarNoduri, numarMuchii;
inFile >> numarNoduri >> numarMuchii;
std::vector<std::vector<bool>> matriceAdiacenta;
matriceAdiacenta.resize(numarNoduri);
std::fill(matriceAdiacenta.begin(), matriceAdiacenta.end(),
std::vector<bool>(numarNoduri, false));
for (uint muchie = 0; muchie < numarMuchii; muchie++) {
uint x, y;
inFile >> x >> y;
matriceAdiacenta[x - 1][y - 1] = true;
}
std::ofstream outFile;
outFile.open("sortaret.out", std::ios::out);
if (outFile.is_open()) {
std::vector<uint> ordine = sortareTopologica(matriceAdiacenta);
std::transform(ordine.begin(), ordine.end(), ordine.begin(), [&](auto& x){ return x + 1; });
for (auto elem : ordine)
outFile << elem << " ";
outFile << "\n";
} else {
std::cerr << "Nu s-a putut scrie in fisier!" << std::endl;
}
} else {
std::cerr << "Nu am putut deschide fisierul!" << std::endl;
}
inFile.close();
return 0;
}