Pagini recente » Cod sursa (job #1566513) | Cod sursa (job #1415580) | Cod sursa (job #2506885) | Cod sursa (job #2810385) | Cod sursa (job #944591)
Cod sursa(job #944591)
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
class graph {
public:
explicit graph(int _size)
: size(_size),
edges(_size) {}
void add_edge(int src, int dst) {
edges[src].push_back(dst);
}
std::vector<int> topological_sort() {
std::vector<int> in_degree(size);
for (auto i = 0; i < size; ++i)
for (auto neighbour : edges[i])
++in_degree[neighbour];
std::queue<int> q;
for (auto i = 0; i < size; ++i)
if (in_degree[i] == 0)
q.push(i);
std::vector<int> result;
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
for (auto neighbour : edges[node]) {
--in_degree[neighbour];
if (in_degree[neighbour] == 0)
q.push(neighbour);
}
}
return result;
}
private:
int size;
std::vector<std::vector<int>> edges;
};
int main()
{
std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");
int N, M;
fin >> N >> M;
graph g(N);
for (int i = 0; i < M; ++i) {
int src, dst;
fin >> src >> dst;
--src, --dst;
g.add_edge(src, dst);
}
auto result = g.topological_sort();
for (auto node : result)
fout << ++node << " ";
fout << "\n";
return 0;
}