Cod sursa(job #3232820)

Utilizator AlexandruTigauTigau Alexandru AlexandruTigau Data 1 iunie 2024 16:37:38
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector <int> v[50001];
queue <int> q;
int gradin[50001];
int main()
{
    int m,n;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
      int x,y;
      in>>x>>y;
      gradin[y]++;
      v[x].push_back(y);
    }
    
    for(int i=1;i<=n;i++)
    {
      if(!gradin[i])
        q.push(i);
    }
    while(!q.empty())
    {
      int x=q.front(); // scot x      x --->  v[x][i]
      out<<x<<" ";
      int l=v[x].size();
      for(int i=0;i<l;i++)
      {
        gradin[v[x][i]]--;
        if(gradin[v[x][i]]==0)
          q.push(v[x][i]);
      }    
      q.pop();    
    }
    return 0;
}