Cod sursa(job #215233)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 17 octombrie 2008 21:17:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <vector>
#define maxim 50001

using namespace std;

vector<int>sir[maxim];
int grad[maxim],sol[maxim],m,n;

void solve()
{
     int zz=1,aux;
     for(int i=1;i<=n;i++)
          if(grad[i]==0)
              sol[zz++]=i;
     for(int j=1;j<=n;j++)
     {
          aux=sol[j];
          for(vector<int>::iterator it=sir[aux].begin();it!=sir[aux].end();it++)
          {
               grad[(*it)]--;
               if (grad[(*it)]==0)
                    sol[zz++]=(*it);
          }
     }
}

int main ()
{
     freopen("sortaret.in","r",stdin);
     freopen("sortaret.out","w",stdout);
     scanf("%d%d",&n,&m);
     int x,y;
     for (int i=0;i<m;i++)
     {
          scanf("%d%d",&x,&y);
          grad[y]++;
          sir[x].push_back(y);
     }
     solve();
     for(int i=1;i<=n;i++)
          printf("%d ",sol[i]);
     fclose(stdout);
     return 0;
}