Cod sursa(job #1066447)

Utilizator vyrtusRadu Criuleni vyrtus Data 24 decembrie 2013 20:10:47
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

struct drum
{
    int x,y;
};

int main()
{
    int n,m;
    int parcurs[50000];  /* Pe care drumuri poti merge*/
    drum a[100000];
    int val[50000];  /* GI al fiecarui nod */

  ifstream fin ("sortaret.in");
  ofstream fout ("sortaret.out");

fin >> n >> m;

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

 for (int i=1; i<=m ;i++)
 {
   fin >> a[i].x >> a[i].y;
       val[a[i].y] += 1;
       parcurs[i] = 1;
 }

 // Noduri cu GI = 0

 deque <int> gi;
 for (int i=1; i<=n; i++)
      if (val[i] == 0)   gi.push_back(i);

while (!gi.empty())
{
    fout << gi.front() << " ";
     for (int i=1;i<=m;i++)
     {
         if (a[i].x == gi.front() && parcurs[i])
         {
             parcurs[i] = 0;
             val[a[i].y] -= 1;
             if (val[a[i].y] == 0) gi.push_back(a[i].y);
         }
     }
   gi.pop_front();
}

    return 0;
}