Cod sursa(job #1202668)

Utilizator robertstrecheStreche Robert robertstreche Data 28 iunie 2014 23:10:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>

#define lmax 50005
#define lmax1 100005

using namespace std;

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

vector <int>v[lmax];

int n,m,nr;

int grad[lmax],sol[lmax];

inline void read()
{
    int x,y;

    f>>n>>m;

    for (int i=1;i<=m;i++)
      {
          f>>x>>y;

          v[x].push_back(y);

          grad[y]++;
      }
}

inline void solve()
{
    vector <int>::iterator it;

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

    for (int i=1;i<=n;i++)
      for (it=v[sol[i]].begin();it<v[sol[i]].end();it++)
         {
             grad[*it]--;

             if (grad[*it]==0)
              sol[++nr]=*it;
         }

}

inline void write()
{
    for (int i=1;i<=n;i++)
     g<<sol[i]<<" ";
}

int main()
{

    read();

    solve();

    write();

   f.close();
   g.close();
}