Cod sursa(job #2797732)

Utilizator StefaniaCriStefania Cristea StefaniaCri Data 10 noiembrie 2021 15:25:43
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
#define MaxN 50100
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector<int> la[MaxN];
int n,m,x,y;
int deg[MaxN];
int coada[MaxN];
void topologic()
{
    vector<int>::iterator it;
   for(int i=1;i<=n;i++)
     if(deg[i]==0) coada[++coada[0]]= i;

   for(int i=1;i<=n;i++)
   {
       int x=coada[i];
       for(it= la[x].begin();it!=la[x].end();++it)
       {
           deg[*it]--;
           if(!deg[*it]) coada[++coada[0]]=*it;
       }
   }
   for(int i=1;i<=n;i++)
     g<<coada[i]<<" ";
}

int main()
{
     f>>n>>m;
     for(int i=0;i<m;i++)
     {
      f>>x>>y;
      la[x].push_back(y);
     }
     f.close();
     topologic();
     g.close();
     return 0;
}