Pagini recente » Cod sursa (job #687420) | Rating Yuzgulen Begum (begy27) | Cod sursa (job #1649851) | Cod sursa (job #1830192) | Cod sursa (job #2206509)
#include <fstream>
#include <queue>
#include <vector>
int main() {
std::ifstream in("sortaret.in");
std::ofstream out("sortaret.out");
int n, m;
in >> n >> m;
std::vector<std::vector<int>> outbound;
std::vector<std::vector<int>> inbound;
std::vector<int> count;
std::vector<int> sorted;
outbound.reserve(n);
inbound.reserve(n);
count.reserve(n);
sorted.reserve(n);
for (int i = 0; i < n; i++) {
outbound.push_back(std::vector<int>());
inbound.push_back(std::vector<int>());
count.push_back(0);
}
for (int i = 0; i < m; i++) {
int from, to;
in >> from >> to;
outbound[from - 1].push_back(to);
inbound[to - 1].push_back(from);
count[to - 1]++;
}
std::queue<int> q;
for (int i = 0; i < n; i++) {
if (count[i] == 0) q.push(i + 1);
}
while (!q.empty()) {
int current = q.front();
q.pop();
sorted.push_back(current);
for (int u : outbound[current - 1]) {
count[u - 1]--;
if (count[u - 1] == 0) q.push(u);
}
}
if (sorted.size() == n) {
for (int i : sorted) {
out << i << " ";
}
} else {
out << "Not a DAG!";
}
return 0;
}