Pagini recente » Cod sursa (job #20027) | Cod sursa (job #1566598) | Cod sursa (job #2024393) | Cod sursa (job #1144285) | Cod sursa (job #1337487)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
vector<short> *successors, sorted;
unsigned short vertex_number, from, to;
int *predecessors_number, edge_number;
queue<short> q;
ifstream in_file("sortaret.in");
in_file >> vertex_number >> edge_number;
successors = new vector<short>[vertex_number];
predecessors_number = new int[vertex_number];
for (unsigned short i = 0; i < vertex_number; ++i)
predecessors_number[i] = 0;
while (edge_number--)
{
in_file >> from >> to;
successors[from - 1].push_back(to - 1);
++predecessors_number[to - 1];
}
in_file.close();
for (unsigned short i = 0; i < vertex_number; ++i)
if (!predecessors_number[i])
q.push(i);
do
{
sorted.push_back(q.front());
for (auto successor : successors[q.front()])
if (!(--predecessors_number[successor]))
q.push(successor);
q.pop();
} while (!q.empty());
ofstream out_file("sortaret.out");
for (auto node : sorted)
out_file << node + 1 << ' ';
delete[] successors;
delete[] predecessors_number;
}