Pagini recente » Cod sursa (job #1161978) | Cod sursa (job #2555220) | Cod sursa (job #2451316) | Cod sursa (job #25260) | Cod sursa (job #2348380)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
using ListaVecini = vector<int>;
using Graf = vector<ListaVecini>;
int main() {
ifstream in{ "sortaret.in" };
int n, m;
in >> n >> m;
Graf graf(n + 1);
Graf incidente(n + 1);
for (int i = 1; i <= m; ++i) {
int start, end;
in >> start >> end;
graf[start].push_back(end);
incidente[end].push_back(start);
}
vector<int> initiale;
for (int i = 1; i <= n; ++i) {
if (incidente[i].empty()) {
initiale.push_back(i);
}
}
vector<int> sortate;
sortate.reserve(n);
while (!initiale.empty()) {
int nod = initiale.back();
initiale.pop_back();
sortate.push_back(nod);
for (int vecin : graf[nod]) {
auto poz = find(incidente[vecin].begin(), incidente[vecin].end(), nod);
incidente[vecin].erase(poz);
if (incidente[vecin].empty()) {
initiale.push_back(vecin);
}
}
}
ofstream out{ "sortaret.out" };
for (int i = 0; i < sortate.size(); ++i) {
out << sortate[i] << ' ';
}
out << '\n';
}