Cod sursa(job #1936167)

Utilizator AndreiDumitrescuAndrei Dumitrescu AndreiDumitrescu Data 22 martie 2017 21:37:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> v[50001];
deque <int> deq;
int n, m , grad[50001];

int main()
{
   int i, j;
   f >> n >> m;
   while(m)
   {
       int x, y;
       f >> x >> y;
       v[x].push_back(y);
       grad[y]++;
       m--;
   }
   for(i = 1 ; i <= n ; i++)
   {
        if(grad[i] == 0)
            deq.push_back(i);
   }
   while(!deq.empty())
   {
       int a;
       a = deq.front();
       for(i = 0 ; i < v[a].size() ; i++)
       {
           grad[v[a][i]]--;
           if(grad[v[a][i]] == 0)
                deq.push_back(v[a][i]);
       }
       g << a << " ";
       deq.pop_front();
   }
}