Pagini recente » Cod sursa (job #20093) | Cod sursa (job #3204468) | Cod sursa (job #162) | Cod sursa (job #10848) | Cod sursa (job #2456084)
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<queue>
const std::string inFileName = "sortaret.in";
const std::string outFileName = "sortaret.out";
const int MAX_EDGES = 50001;
std::vector<int> sort(std::vector<int>& cntInputs, std::vector<std::vector<int>>& vertices) {
std::queue<int> q;
std::vector<int> sorted(cntInputs.size() - 1);
int inserted = 0;
for (size_t i = 1; i < cntInputs.size(); ++i) {
if (!cntInputs[i]) {
q.push(i);
sorted[inserted++] = i;
}
}
while (!q.empty()) {
int node = q.front();
q.pop();
for (auto& n : vertices[node]) {
if (!cntInputs[n]) {
continue;
}
cntInputs[n] --;
if (!cntInputs[n]) {
q.push(n);
sorted[inserted++] = n;
}
}
}
//if inserted < sorted.size() means that there we have a cycle
return std::move(sorted);
}
int main() {
int n, m;
std::ifstream in(inFileName);
std::ofstream out(outFileName);
in >> n >> m;
std::vector<int> cntInputs(n + 1);
std::vector<std::vector<int>> vertices(n + 1);
for (size_t x, y, i = 1; i <= m; ++i) {
in >> x >> y;
cntInputs[y] ++;
vertices[x].push_back(y);
}
std::vector<int> sorted = sort(cntInputs, vertices);
for (auto& node : sorted) {
out << node << ' ';
}
return 0;
}