Pagini recente » Cod sursa (job #2019132) | Cod sursa (job #571956) | Cod sursa (job #2398769) | Cod sursa (job #2661302) | Cod sursa (job #2331448)
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<int> ns[50005];
queue<int> q;
int extg[50005], solution[50005], solutionNodes;
void topSort() {
while (!q.empty()) {
int currentNode = q.front(); q.pop();
// cout << currentNode << ' ';
solution[solutionNodes++] = currentNode;
vector<int>::iterator i;
for (i = ns[currentNode].begin(); i < ns[currentNode].end(); i++) {
extg[*i]--;
if (!extg[*i])
q.push(*i);
}
}
}
int main () {
int nodes, edges, end1, end2;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
fi >> nodes >> edges;
for (int edge = 1; edge <= edges; edge++)
fi >> end1 >> end2, ns[end1].push_back(end2), extg[end2]++;
for (int node = 1; node <= nodes; node++)
if (!extg[node])
q.push(node);
topSort();
for (int index = 0; index < nodes; index++)
fo << solution[index] << ' ';
return 0;
}