Pagini recente » Cod sursa (job #1095055) | Cod sursa (job #843994) | Cod sursa (job #2541882) | Cod sursa (job #499969) | Cod sursa (job #2317216)
#include <fstream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int VMAX = 50000;
list <int> adjList[1 + VMAX];
vector <int> inDeg;
int V, E;
void readData() {
fin >> V >> E;
inDeg.resize(1 + V);
for (; E; --E) {
int from, to;
fin >> from >> to;
adjList[from].push_back(to);
++inDeg[to];
}
}
void topoSort() {
deque <int> Queue;
for (int node = 1; node <= V; ++node)
if (inDeg[node] == 0)
Queue.push_back(node);
while (!Queue.empty()) {
int node = Queue.front();
Queue.pop_front();
fout << node << ' ';
for (const int &nextNode : adjList[node]) {
--inDeg[nextNode];
if (inDeg[nextNode] == 0)
Queue.push_back(nextNode);
}
}
}
int main() {
readData();
topoSort();
}