Pagini recente » Cod sursa (job #2188779) | Cod sursa (job #1632952) | Cod sursa (job #1083173) | Cod sursa (job #1917269) | Cod sursa (job #1234264)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
std::queue<int> noIncomingEdges(const std::vector< std::list<int> > &in_list)
{
std::queue<int> ret_list;
for (std::vector< std::list<int> >::const_iterator 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(std::vector< std::list<int> > &in_list,
std::vector< std::list<int> > &out_list)
{
std::queue<int> no_inc_edges = noIncomingEdges(in_list);
std::list<int> ret_list;
while (!no_inc_edges.empty()) {
int vertex = no_inc_edges.front();
no_inc_edges.pop();
ret_list.push_back(vertex);
for (std::list<int>::const_iterator 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);
}
}
if (!in_list.front().empty()) {
std::cerr << "Graph has cycles!" << std::endl;
return std::list<int>();
}
return ret_list;
}
int main()
{
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
int N, M;
in >> N >> M;
std::vector< std::list<int> > in_list(N);
std::vector< std::list<int> > out_list(N);
for (int i = 0; i < M; ++i) {
int x, y;
in >> x >> y;
out_list[x-1].push_front(y-1);
in_list[y-1].push_front(x-1);
}
in.close();
std::list<int> ordered = sorttopo(in_list, out_list);
for (auto &i : ordered)
out << i+1 << " ";
out.close();
return 0;
}