Cod sursa(job #215739)

Utilizator rethosPaicu Alexandru rethos Data 20 octombrie 2008 18:11:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#define NM 500001
int n,m;
struct list{int nod;list *urm;} *g[NM];
int grad[NM],viz[NM];
/********/
void df(int k)
{printf("%d ",k);
 viz[k]=1;
 list *p;
 for (p=g[k];p;p=p->urm)
        {grad[p->nod]--;
         if (grad[p->nod]==0) df(p->nod);
        }
}
/********/
inline void add(int x,int y)
{list *p=new list;
 p->nod=y;
 p->urm=g[x];
 g[x]=p;
}
/********/
int main()
{freopen("sortaret.in","r",stdin);
 freopen("sortaret.out","w",stdout);
 int i,x,y;
 scanf("%d %d",&n,&m);
 for (i=1;i<=m;i++)
        {scanf("%d %d",&x,&y);
         add(x,y);
         grad[y]++;
        }
 for (i=1;i<=n;i++)
        {if (grad[i]==0&&viz[i]==0)
                df(i);
        }
 return 0;
}