Pagini recente » Cod sursa (job #1515865) | Cod sursa (job #295767) | Cod sursa (job #879049) | Cod sursa (job #2830398) | Cod sursa (job #2731746)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define Nmax 50001
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> graph[Nmax];
vector<int> top;
queue<int> q;
int d[Nmax];
int main()
{
int n, m, i, x, y;
in >> n >> m;
for(i = 0; i < m; i++) {
in >> x >> y;
// graf orientat
graph[x].push_back(y);
// gradul interior al nodului y
d[y]++;
}
// inserez in coada nodurile i cu d[i] == 0
for (i = 1; i <= n; i++) {
if (!d[i]) {
// inserez in coada nodul i
q.push(i);
}
}
while(!q.empty()) {
x = q.front(); // extrag primul element din coada
q.pop(); // elimin primul element din coada
// adaug nodul de la inceputul cozii in solutia pentru sortarea topologica
top.push_back(x);
// parcurg vecinii y ai nodului x
for (i = 0; i < graph[x].size(); i++) {
y = graph[x][i];
// reduc cu 1 gradul nodului
d[y]--;
if (d[y] == 0) {
// inserare in coada
q.push(y);
}
}
}
for (i = 0; i < top.size(); i++) {
out << top[i] << " ";
}
out << '\n';
return 0;
}