Pagini recente » Cod sursa (job #2631667) | Cod sursa (job #935974) | Cod sursa (job #291097) | Cod sursa (job #1919638) | Cod sursa (job #1439660)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
#define MAX 50010
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> solution;
vector<int> graph[MAX];
int incomingEdges[MAX];
int n;
inline void sortTopologically() {
queue<int> q;
for (int i = 0; i < n; i++) {
if (incomingEdges[i] == 0) {
q.push(i);
solution.push_back(i);
}
}
while (!q.empty()) {
int currentNode = q.front();
q.pop();
for (unsigned int i = 0; i < graph[currentNode].size(); i++) {
int neighbour = graph[currentNode].at(i);
incomingEdges[neighbour]--;
if (incomingEdges[neighbour] == 0) {
q.push(neighbour);
solution.push_back(neighbour);
}
}
}
}
inline void printSolution() {
for (unsigned int i = 0; i < solution.size(); i++) {
out << solution.at(i) + 1 << " ";
}
}
int main() {
int m, n1, n2;
in >> n >> m;
for (int i = 0; i < m; i++) {
in >> n1 >> n2;
graph[n1 - 1].push_back(n2 - 1);
incomingEdges[n2 - 1]++;
}
sortTopologically();
printSolution();
return 0;
}