Cod sursa(job #2216009)

Utilizator Iulia25Hosu Iulia Iulia25 Data 24 iunie 2018 15:43:09
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

int n, m, x, y, grad[50001];
queue <int> nodes, g[50001];

int main()  {
  fin >> n >> m;
  for (int i = 1; i <= m; ++i)  {
    fin >> x >> y;
    g[x].push(y);
    ++grad[y];
  }
  for (int i = 1; i <= n; ++i)  {
    if (grad[i] == 0)
      nodes.push(i);
  }
  while (!nodes.empty())  {
    int nod = nodes.front();
    while (!g[nod].empty()) {
      if (--grad[g[nod].front()] == 0)
        nodes.push(g[nod].front());
      g[nod].pop();
    }
    fout << nod << ' ';
    nodes.pop();
  }
}