Cod sursa(job #1073301)

Utilizator vyrtusRadu Criuleni vyrtus Data 5 ianuarie 2014 21:58:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

vector <int> drum[100001];
int val[50001];  /* GI al fiecarui nod */
 deque <int> coada;

int main()
{
    long n,m;

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

f >> n >> m;

  for (int i=1; i<=n; i++)
     val[i] = 0;

 for (long i=1; i<=m ;i++)
 {
      int x,y;
   f >> x >> y;
       val[y]++;
       drum[x].push_back(y);
 }

 for (int i=1; i<=n; i++)
 {
      if (val[i] == 0) { coada.push_back(i);   g << i << " "; }
 }

 while (!coada.empty())
{
    int nod = coada.front();
     coada.pop_front();
     for (int i=0; i< drum[nod].size(); ++i)
     {
         int t = drum[nod][i];
        --val[t];
         if (val[t] == 0)
         {
            coada.push_back(t);
            g << t << " ";
         }
     }
}

    return 0;
}