Cod sursa(job #518435)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 31 decembrie 2010 18:00:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
#include<stdlib.h>
#define NR 50001
typedef struct nod
{long info;
struct nod *next;}Nod;
typedef Nod *list;
list l[NR],q,s;
long n,i,j,k,m,c[NR],t,v[NR],g[NR];

void add(list &l,long x)
{nod *nou=new nod;
nou->info=x;
nou->next=l;
l=nou;}

int apartine(list l,long x)
{list c;
for(c=l;c!=NULL;c=c->next)
if(c->info==x)
         return 1;
return 0;}

long del(list &l)
{Nod *aux=l->next;
long x=l->info;
free(l);
l=aux;
return x;}

int main()
{freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
       {c[i]=0;
       l[i]=NULL;
       g[i]=0;}
for(k=1;k<=m;k++)
       {scanf("%ld%ld",&i,&j);
       g[i]++;
       if(apartine(l[i],j)==0)
                add(l[i],j);}
for(i=1;i<=n;i++)
if(g[i]==0)
       {s=NULL;
       add(s,i);
       while(s!=NULL)
               {j=del(s);
               c[j]=1;
               q=l[j];
               while(q!=NULL)
                       {t=del(q);
                       if(c[t]==0)
                              add(s,t);}}
       printf("%ld ",i);}      
fclose(stdin);
fclose(stdout);
return 0;}