Cod sursa(job #3336958)

Utilizator andrei0925Andrei Perdevara andrei0925 Data 26 ianuarie 2026 19:58:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
int N, M, x, y, grad[50005];
vector <int> G[50005];
vector <int> top_sort;
queue <int> q;
int main()
{
  cin >> N >> M;
  for(int i = 1; i <= M; i++)
  {
    cin >> x >> y;
    G[x].push_back(y);
    grad[y]++;
  }
  for(int i = 1; i <= N; i++)
  {
    if(grad[i] == 0)
      q.push(i);
  }
  while(q.size())
  {
    int acc = q.front();
    q.pop();
    top_sort.push_back(acc);
    for(auto e : G[acc])
    {
      grad[e]--;
      if(grad[e] == 0)
        q.push(e);
    }
  }
  for( auto e : top_sort )
    cout << e <<' ';
  return 0;
}