Pagini recente » Cod sursa (job #1631096) | Cod sursa (job #456662) | Cod sursa (job #390313) | Cod sursa (job #540293) | Cod sursa (job #3032460)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");
int n;
vector<int> G[50001];
int grd[50001]; // nr de noduri incidente spre 'i'
int main()
{
int m;
fin >> n >> m;
for (int i=0; i<m; i++) {
int a, b;
fin >> a >> b;
G[a].push_back(b);
grd[b]++;
}
vector<int> result;
result.reserve(n);
// step 1. Add everything with a degree of 0 to 'q'
queue<int> q;
for (int i=1; i<=n; i++) {
if (grd[i] == 0)
q.push(i);
}
while (!q.empty())
{
int x = q.front();
q.pop();
result.push_back(x);
for (int i : G[x])
{
grd[i]--;
if (grd[i] == 0)
q.push(i);
}
}
for (int i : result)
{
fout << i << ' ';
}
return 0;
}