Cod sursa(job #282453)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 17 martie 2009 17:44:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
//Cica o clatita mergea prin desert... si ghici ce? :-O :-O
//ia cazut gemu :(((
//BC
#include <stdio.h>

using namespace std;

struct nod
{
     int inf;
     nod *next;
}*sir[50010];

int rez[50010],nr,grad[50010],n,m;

void baga(int a,int b)
{
     nod *q=new nod;
     q->inf=a;
     q->next=sir[b];
     sir[b]=q;
}

void citire()
{
     scanf ("%d %d",&n,&m);
     int a,b;
     for (int i=0;i<m;i++)
     {
               scanf ("%d %d",&a,&b);
               baga(b,a);
               grad[b]++;
     }
}

void solve()
{
     for (int i=1;i<=n;i++)
          if (grad[i]==0)
               rez[nr++]=i;

     for (int i=0;i<nr;i++)
     {
          for (nod *j=sir[rez[i]];j;j=j->next)
          {
               grad[j->inf]--;
               if (grad[j->inf]==0)
               {
                    rez[nr++]=j->inf;
               }
          }
     }
     for (int i=0;i<n;i++)
          printf("%d ",rez[i]);
     printf("\n");
}

int main ()
{
     freopen ("sortaret.in","r",stdin);
     freopen ("sortaret.out","w",stdout);
     citire();
     solve();
     return 0;
}