Cod sursa(job #368186)

Utilizator irene_mFMI Irina Iancu irene_m Data 24 noiembrie 2009 08:22:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#define MaxN 50024

struct muchie{
      int x;
      muchie *urm;
}     *G[MaxN];

int N,st[MaxN],nr,uz[MaxN];

void add(int x,int y)
{
      muchie *q=new muchie;
      q->x=y; q->urm=G[x]; G[x]=q;
}

void cit()
{
      int i,x,y,M;
      freopen("sortaret.in","r",stdin);
      scanf("%d%d",&N,&M);
      for(i=1;i<=M;i++)
      {
            scanf("%d%d",&x,&y);
            add(x,y);
            //add(y,x);
      }
}

void df(int nod)
{
      muchie *q=new muchie;
      uz[nod]=1;

      for(q=G[nod]; q; q=q->urm)
            if(!uz[q->x])
                  df(q->x);
      st[++nr]=nod;
}

void afis()
{
      freopen("sortaret.out","w",stdout);
      for(int i=N;i>0;i--)
            printf("%d ",st[i]);
}

int main()
{
      cit();
      for(int i=1;i<=N;i++)
            if(!uz[i])
                  df(i);
      afis();
      return 0;
}