Cod sursa(job #213941)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 12 octombrie 2008 10:23:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
//sort top
#include <fstream>
#include <vector>
#define lg_max 50001

using namespace std;

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

vector <int> V[lg_max];

int grad[lg_max],val_final[lg_max];
int n,m;

void citire()
{
     fin>>n>>m;
     int x,y;
     for (int i=0;i<m;i++)
     {
          fin>>x>>y;
          grad[y]++;
          V[x].push_back(y);
     }
}

void rezolvare()
{
     int nr=1,aux;

     for (int i=1;i<=n;i++)
          if (grad[i]==0)
               val_final[nr++]=i;

     for (int j=1;j<=n;j++)
     {
          aux=val_final[j];
          for (vector<int>::iterator it=V[aux].begin() ;it!=V[aux].end() ;it++)
          {
               grad[(*it)]--;
               if (grad[(*it)]==0)
                    val_final[nr++]=(*it);
          }
     }
}

void afisare()
{
     for (int i=1;i<=n;i++)
          fout<<val_final[i]<<" ";
     fout<<"\n";
}

int main ()
{
     citire();
     rezolvare();
     afisare();
     return 0;
}