Pagini recente » Cod sursa (job #1430546) | Cod sursa (job #1432395) | Cod sursa (job #1432645) | Cod sursa (job #1416549) | Cod sursa (job #1416548)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <unordered_set>
using AdjList = std::vector<std::list<int>>;
std::queue<int> noIncomingEdges(const AdjList &in_list)
{
std::queue<int> ret_list;
for (auto it = in_list.cbegin(); it != in_list.cend(); ++it)
if (it->empty())
ret_list.push(it - in_list.cbegin());
return ret_list;
}
std::list<int> sorttopo(AdjList &in_list, const AdjList &out_list)
{
auto no_inc_edges = noIncomingEdges(in_list);
std::list<int> ret_list;
while (!no_inc_edges.empty()) {
auto vertex = no_inc_edges.front();
no_inc_edges.pop();
ret_list.push_back(vertex);
for (auto it = out_list[vertex].cbegin(); it != out_list[vertex].cend();
++it) {
in_list[*it].remove(vertex);
if (in_list[*it].empty())
no_inc_edges.push(*it);
}
}
return !in_list.front().empty() ? std::list<int>{} : ret_list;
}
int main()
{
std::ifstream in{"sortaret.in"};
std::ofstream out{"sortaret.out"};
int N, M;
in >> N >> M;
AdjList in_list(N);
AdjList out_list(N);
for (auto i = 0; i < M; ++i) {
int x, y;
in >> x >> y;
in_list[y - 1].push_front(x - 1);
out_list[x - 1].push_front(y - 1);
}
for (auto i = 0; i < N; ++i) {
in_list[i].unique();
out_list[i].unique();
}
auto ordered = sorttopo(in_list, out_list);
if (ordered.empty()) {
std::cerr << "Graph has cycles!" << std::endl;
return 1;
}
for (auto &i : ordered)
out << i + 1 << " ";
return 0;
}